<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 5.5</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 5.5" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 5.5" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-5.xhtml#Chapter-5" rel="prev" title="Chapter 5" />
<link href="References.xhtml#References" rel="next" title="References" />
<link href="5_002e4.xhtml#g_t5_002e4_002e4" rel="prev" title="5.4.4" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t5_002e5"></a>
<nav class="header">
<p>
Next: <a href="References.xhtml#References" accesskey="n" rel="next">References</a>, Prev: <a href="5_002e4.xhtml#g_t5_002e4" accesskey="p" rel="prev">5.4</a>, Up: <a href="Chapter-5.xhtml#Chapter-5" accesskey="u" rel="prev">Chapter 5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Compilation"></a>
<h3 class="section"><span class="secnum">5.5</span><span class="sectitle">Compilation</span></h3>

<p>The explicit-control evaluator of <a href="5_002e4.xhtml#g_t5_002e4">5.4</a> is a register machine whose
controller interprets Scheme programs.  In this section we will see how to run
Scheme programs on a register machine whose controller is not a Scheme
interpreter.
</p>
<p>The explicit-control evaluator machine is universal—it can carry out any
computational process that can be described in Scheme.  The evaluator’s
controller orchestrates the use of its data paths to perform the desired
computation.  Thus, the evaluator’s data paths are universal: They are
sufficient to perform any computation we desire, given an appropriate
controller.<a class="footnote_link" id="DOCF318" href="#FOOT318"><sup>318</sup></a>
</p>
<p>Commercial general-purpose computers are register machines organized around a
collection of registers and operations that constitute an efficient and
convenient universal set of data paths.  The controller for a general-purpose
machine is an interpreter for a register-machine language like the one we have
been using.  This language is called the <a id="index-native-language"></a>
<em>native language</em> of the
machine, or simply <a id="index-machine-language"></a>
<em>machine language</em>.  Programs written in machine
language are sequences of instructions that use the machine’s data paths.  For
example, the explicit-control evaluator’s instruction sequence can be thought
of as a machine-language program for a general-purpose computer rather than as
the controller for a specialized interpreter machine.
</p>
<p>There are two common strategies for bridging the gap between higher-level
languages and register-machine languages.  The explicit-control evaluator
illustrates the strategy of interpretation.  An interpreter written in the
native language of a machine configures the machine to execute programs written
in a language (called the <a id="index-source-language"></a>
<em>source language</em>) that may differ from the
native language of the machine performing the evaluation.  The primitive
procedures of the source language are implemented as a library of subroutines
written in the native language of the given machine.  A program to be
interpreted (called the <a id="index-source-program"></a>
<em>source program</em>) is represented as a data
structure.  The interpreter traverses this data structure, analyzing the source
program.  As it does so, it simulates the intended behavior of the source
program by calling appropriate primitive subroutines from the library.
</p>
<p>In this section, we explore the alternative strategy of <a id="index-compilation"></a>
<em>compilation</em>.
A compiler for a given source language and machine translates a source program
into an equivalent program (called the <a id="index-object-program"></a>
<em>object program</em>) written in the
machine’s native language.  The compiler that we implement in this section
translates programs written in Scheme into sequences of instructions to be
executed using the explicit-control evaluator machine’s data
paths.<a class="footnote_link" id="DOCF319" href="#FOOT319"><sup>319</sup></a>
</p>
<p>Compared with interpretation, compilation can provide a great increase in the
efficiency of program execution, as we will explain below in the overview of
the compiler.  On the other hand, an interpreter provides a more powerful
environment for interactive program development and debugging, because the
source program being executed is available at run time to be examined and
modified.  In addition, because the entire library of primitives is present,
new programs can be constructed and added to the system during debugging.
</p>
<p>In view of the complementary advantages of compilation and interpretation,
modern program-development environments pursue a mixed strategy.  Lisp
interpreters are generally organized so that interpreted procedures and
compiled procedures can call each other.  This enables a programmer to compile
those parts of a program that are assumed to be debugged, thus gaining the
efficiency advantage of compilation, while retaining the interpretive mode of
execution for those parts of the program that are in the flux of interactive
development and debugging.  In <a href="#g_t5_002e5_002e7">5.5.7</a>, after we have implemented
the compiler, we will show how to interface it with our interpreter to produce
an integrated interpreter-compiler development system.
</p>
<a id="An-overview-of-the-compiler"></a>
<h5 class="subsubheading">An overview of the compiler</h5>

<p>Our compiler is much like our interpreter, both in its structure and in the
function it performs.  Accordingly, the mechanisms used by the compiler for
analyzing expressions will be similar to those used by the interpreter.
Moreover, to make it easy to interface compiled and interpreted code, we will
design the compiler to generate code that obeys the same conventions of
register usage as the interpreter: The environment will be kept in the
<code>env</code> register, argument lists will be accumulated in <code>argl</code>, a
procedure to be applied will be in <code>proc</code>, procedures will return their
answers in <code>val</code>, and the location to which a procedure should return will
be kept in <code>continue</code>.  In general, the compiler translates a source
program into an object program that performs essentially the same register
operations as would the interpreter in evaluating the same source program.
</p>
<p>This description suggests a strategy for implementing a rudimentary compiler:
We traverse the expression in the same way the interpreter does.  When we
encounter a register instruction that the interpreter would perform in
evaluating the expression, we do not execute the instruction but instead
accumulate it into a sequence.  The resulting sequence of instructions will be
the object code.  Observe the efficiency advantage of compilation over
interpretation.  Each time the interpreter evaluates an expression—for
example, <code>(f 84 96)</code>—it performs the work of classifying the expression
(discovering that this is a procedure application) and testing for the end of
the operand list (discovering that there are two operands).  With a compiler,
the expression is analyzed only once, when the instruction sequence is
generated at compile time.  The object code produced by the compiler contains
only the instructions that evaluate the operator and the two operands, assemble
the argument list, and apply the procedure (in <code>proc</code>) to the arguments
(in <code>argl</code>).
</p>
<p>This is the same kind of optimization we implemented in the analyzing evaluator
of <a href="4_002e1.xhtml#g_t4_002e1_002e7">4.1.7</a>.  But there are further opportunities to gain efficiency
in compiled code.  As the interpreter runs, it follows a process that must be
applicable to any expression in the language.  In contrast, a given segment of
compiled code is meant to execute some particular expression.  This can make a
big difference, for example in the use of the stack to save registers.  When
the interpreter evaluates an expression, it must be prepared for any
contingency.  Before evaluating a subexpression, the interpreter saves all
registers that will be needed later, because the subexpression might require an
arbitrary evaluation.  A compiler, on the other hand, can exploit the structure
of the particular expression it is processing to generate code that avoids
unnecessary stack operations.
</p>
<p>As a case in point, consider the combination <code>(f 84 96)</code>.  Before the
interpreter evaluates the operator of the combination, it prepares for this
evaluation by saving the registers containing the operands and the environment,
whose values will be needed later.  The interpreter then evaluates the operator
to obtain the result in <code>val</code>, restores the saved registers, and finally
moves the result from <code>val</code> to <code>proc</code>.  However, in the particular
expression we are dealing with, the operator is the symbol <code>f</code>, whose
evaluation is accomplished by the machine operation
<code>lookup-variable-value</code>, which does not alter any registers.  The compiler
that we implement in this section will take advantage of this fact and generate
code that evaluates the operator using the instruction
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign proc 
        </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">const f</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span></pre></div>

<p>This code not only avoids the unnecessary saves and restores but also assigns
the value of the lookup directly to <code>proc</code>, whereas the interpreter would
obtain the result in <code>val</code> and then move this to <code>proc</code>.
</p>
<p>A compiler can also optimize access to the environment.  Having analyzed the
code, the compiler can in many cases know in which frame a particular variable
will be located and access that frame directly, rather than performing the
<code>lookup-variable-value</code> search.  We will discuss how to implement such
variable access in <a href="#g_t5_002e5_002e6">5.5.6</a>.  Until then, however, we will focus on
the kind of register and stack optimizations described above.  There are many
other optimizations that can be performed by a compiler, such as coding
primitive operations “in line” instead of using a general <code>apply</code>
mechanism (see <a href="#Exercise-5_002e38">Exercise 5.38</a>); but we will not emphasize these here.  Our
main goal in this section is to illustrate the compilation process in a
simplified (but still interesting) context.
</p>

<a id="g_t5_002e5_002e1"></a>
<a id="Structure-of-the-Compiler"></a>
<h4 class="subsection"><span class="secnum">5.5.1</span><span class="sectitle">Structure of the Compiler</span></h4>

<p>In <a href="4_002e1.xhtml#g_t4_002e1_002e7">4.1.7</a> we modified our original metacircular interpreter to
separate analysis from execution.  We analyzed each expression to produce an
execution procedure that took an environment as argument and performed the
required operations.  In our compiler, we will do essentially the same
analysis.  Instead of producing execution procedures, however, we will generate
sequences of instructions to be run by our register machine.
</p>
<p>The procedure <code>compile</code> is the top-level dispatch in the compiler.  It
corresponds to the <code>eval</code> procedure of <a href="4_002e1.xhtml#g_t4_002e1_002e1">4.1.1</a>, the
<code>analyze</code> procedure of <a href="4_002e1.xhtml#g_t4_002e1_002e7">4.1.7</a>, and the <code>eval-dispatch</code>
entry point of the explicit-control-evaluator in <a href="5_002e4.xhtml#g_t5_002e4_002e1">5.4.1</a>.  The
compiler, like the interpreters, uses the expression-syntax procedures defined
in <a href="4_002e1.xhtml#g_t4_002e1_002e2">4.1.2</a>.<a class="footnote_link" id="DOCF320" href="#FOOT320"><sup>320</sup></a>  <code>Compile</code> performs a
case analysis on the syntactic type of the expression to be compiled.  For each
type of expression, it dispatches to a specialized <a id="index-code-generator"></a>
<em>code generator</em>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">self-evaluating? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-self-evaluating 
          exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">quoted? exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">compile-quoted exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">variable? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-variable 
          exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">assignment? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-assignment
          exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">definition? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-definition
          exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">if</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-if exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-lambda exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">begin</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-sequence 
          </span><span class="opn">(</span><span class="pln">begin-actions exp</span><span class="clo">)</span><span class="pln"> target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">cond</span><span class="pun">?</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">compile 
          </span><span class="opn">(</span><span class="pln">cond-</span><span class="pun">&gt;</span><span class="kwd">if</span><span class="pln"> exp</span><span class="clo">)</span><span class="pln"> target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">application? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">compile-application 
          exp target linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown expression type: 
                 COMPILE"</span><span class="pln"> 
                exp</span><span class="clo">))))</span></pre></div>

<a id="Targets-and-linkages"></a>
<h5 class="subsubheading">Targets and linkages</h5>

<p><code>Compile</code> and the code generators that it calls take two arguments in
addition to the expression to compile.  There is a <a id="index-target"></a>
<em>target</em>, which
specifies the register in which the compiled code is to return the value of the
expression.  There is also a <a id="index-linkage-descriptor"></a>
<em>linkage descriptor</em>, which describes how
the code resulting from the compilation of the expression should proceed when
it has finished its execution.  The linkage descriptor can require that the
code do one of the following three things:
</p>
<ul>
<li> continue at the next instruction in sequence (this is specified by the linkage
descriptor <code>next</code>),

</li><li> return from the procedure being compiled (this is specified by the linkage
descriptor <code>return</code>), or

</li><li> jump to a named entry point (this is specified by using the designated label as
the linkage descriptor).

</li></ul>

<p>For example, compiling the expression <code>5</code> (which is self-evaluating) with
a target of the <code>val</code> register and a linkage of <code>next</code> should produce
the instruction
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">5</span><span class="clo">))</span></pre></div>

<p>Compiling the same expression with a linkage of <code>return</code> should produce
the instructions
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">5</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span></pre></div>

<p>In the first case, execution will continue with the next instruction in the
sequence. In the second case, we will return from a procedure call.  In both
cases, the value of the expression will be placed into the target <code>val</code>
register.
</p>
<a id="Instruction-sequences-and-stack-usage"></a>
<h5 class="subsubheading">Instruction sequences and stack usage</h5>

<p>Each code generator returns an <a id="index-instruction-sequence"></a>
<em>instruction sequence</em> containing the
object code it has generated for the expression.  Code generation for a
compound expression is accomplished by combining the output from simpler code
generators for component expressions, just as evaluation of a compound
expression is accomplished by evaluating the component expressions.
</p>
<p>The simplest method for combining instruction sequences is a procedure called
<code>append-instruction-sequences</code>.  It takes as arguments any number of
instruction sequences that are to be executed sequentially; it appends them and
returns the combined sequence.  That is, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>s</mi>
    <mi>e</mi>
    <msub>
      <mi>q</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> 
and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>s</mi>
    <mi>e</mi>
    <msub>
      <mi>q</mi>
      <mn>2</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> are sequences of instructions, then 
evaluating
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">append-instruction-sequences ⟨</span><var><span class="pln">seq</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">seq</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>produces the sequence
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><var><span class="pln">seq</span><span class="pun">₁</span></var><span class="pln">⟩
⟨</span><var><span class="pln">seq</span><span class="pun">₂</span></var><span class="pln">⟩</span></pre></div>

<p>Whenever registers might need to be saved, the compiler’s code generators use
<code>preserving</code>, which is a more subtle method for combining instruction
sequences.  <code>Preserving</code> takes three arguments: a set of registers and two
instruction sequences that are to be executed sequentially.  It appends the
sequences in such a way that the contents of each register in the set is
preserved over the execution of the first sequence, if this is needed for the
execution of the second sequence.  That is, if the first sequence modifies the
register and the second sequence actually needs the register’s original
contents, then <code>preserving</code> wraps a <code>save</code> and a <code>restore</code> of
the register around the first sequence before appending the sequences.
Otherwise, <code>preserving</code> simply returns the appended instruction sequences.
Thus, for example,
<code>(preserving (list ⟨<var>reg₁</var>⟩ ⟨<var>reg₂</var>⟩) ⟨<var>seg₁</var>⟩ ⟨<var>seg₂</var>⟩)</code>
produces one of the following four sequences of instructions, depending on how
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>s</mi>
    <mi>e</mi>
    <msub>
      <mi>q</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>s</mi>
    <mi>e</mi>
    <msub>
      <mi>q</mi>
      <mn>2</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> 
use <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>r</mi>
    <mi>e</mi>
    <msub>
      <mi>g</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.1em"/>
    <mi>r</mi>
    <mi>e</mi>
    <msub>
      <mi>g</mi>
      <mn>2</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math>:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mtable columnalign="left left left left" rowspacing="4pt" columnspacing="1em" columnlines="solid solid solid">
  <mtr>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
    <mtd>
      <mtext>(save</mtext>
    </mtd>
    <mtd>
      <mtext>(save</mtext>
    </mtd>
    <mtd>
      <mtext>(save</mtext>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
  </mtr>
  <mtr>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
    <mtd>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
    <mtd>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
    <mtd>
      <mtext>(save</mtext>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
  </mtr>
  <mtr>
    <mtd/>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
  </mtr>
  <mtr>
    <mtd/>
    <mtd>
      <mtext>(restore</mtext>
    </mtd>
    <mtd>
      <mtext>(restore</mtext>
    </mtd>
    <mtd>
      <mtext>(restore</mtext>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
  </mtr>
  <mtr>
    <mtd/>
    <mtd>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>1</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
    <mtd>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
    <mtd>
      <mtext>(restore</mtext>
      <mspace width="1ex"/>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>r</mi>
        <mi>e</mi>
        <msub>
          <mi>g</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
      <mtext>)</mtext>
    </mtd>
  </mtr>
  <mtr>
    <mtd/>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
    <mtd>
      <mo stretchy="false">⟨</mo>
      <mspace width="0.1em"/>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>s</mi>
        <mi>e</mi>
        <msub>
          <mi>q</mi>
          <mn>2</mn>
        </msub>
      </mrow>
      <mo stretchy="false">⟩</mo>
    </mtd>
  </mtr>
</mtable>
</math>
</p>
<p>By using <code>preserving</code> to combine instruction sequences the compiler avoids
unnecessary stack operations.  This also isolates the details of whether or not
to generate <code>save</code> and <code>restore</code> instructions within the
<code>preserving</code> procedure, separating them from the concerns that arise in
writing each of the individual code generators.  In fact no <code>save</code> or
<code>restore</code> instructions are explicitly produced by the code generators.
</p>
<p>In principle, we could represent an instruction sequence simply as a list of
instructions.  <code>Append-instruction-sequences</code> could then combine
instruction sequences by performing an ordinary list <code>append</code>.  However,
<code>preserving</code> would then be a complex operation, because it would have to
analyze each instruction sequence to determine how the sequence uses its
registers.  <code>Preserving</code> would be inefficient as well as complex, because
it would have to analyze each of its instruction sequence arguments, even
though these sequences might themselves have been constructed by calls to
<code>preserving</code>, in which case their parts would have already been analyzed.
To avoid such repetitious analysis we will associate with each instruction
sequence some information about its register use.  When we construct a basic
instruction sequence we will provide this information explicitly, and the
procedures that combine instruction sequences will derive register-use
information for the combined sequence from the information associated with the
component sequences.
</p>
<p>An instruction sequence will contain three pieces of information:
</p>
<ul>
<li> the set of registers that must be initialized before the instructions in the
sequence are executed (these registers are said to be <a id="index-needed"></a>
<em>needed</em> by the
sequence),

</li><li> the set of registers whose values are modified by the instructions in the
sequence, and

</li><li> the actual instructions (also called <a id="index-statements"></a>
<em>statements</em>) in the sequence.

</li></ul>

<p>We will represent an instruction sequence as a list of its three parts.  The
constructor for instruction sequences is thus
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
         needs modifies statements</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list needs modifies statements</span><span class="clo">))</span></pre></div>

<p>For example, the two-instruction sequence that looks up the value of the
variable <code>x</code> in the current environment, assigns the result to <code>val</code>,
and then returns, requires registers <code>env</code> and <code>continue</code> to have
been initialized, and modifies register <code>val</code>.  This sequence would
therefore be constructed as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">make-instruction-sequence
 </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env continue</span><span class="clo">)</span><span class="pln">
 </span><span class="lit">'</span><span class="opn">(</span><span class="pln">val</span><span class="clo">)</span><span class="pln">
 </span><span class="lit">'</span><span class="opn">((</span><span class="pln">assign val
           </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const x</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))))</span></pre></div>

<p>We sometimes need to construct an instruction sequence with no statements:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-instruction-sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">make-instruction-sequence </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)))</span></pre></div>

<p>The procedures for combining instruction sequences are shown in 
<a href="#g_t5_002e5_002e4">5.5.4</a>.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e31"></a>Exercise 5.31:</strong> In evaluating a procedure
application, the explicit-control evaluator always saves and restores the
<code>env</code> register around the evaluation of the operator, saves and restores
<code>env</code> around the evaluation of each operand (except the final one), saves
and restores <code>argl</code> around the evaluation of each operand, and saves and
restores <code>proc</code> around the evaluation of the operand sequence.  For each
of the following combinations, say which of these <code>save</code> and
<code>restore</code> operations are superfluous and thus could be eliminated by the
compiler’s <code>preserving</code> mechanism:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">f </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'y</span><span class="clo">)</span><span class="pln">
</span><span class="opn">((</span><span class="pln">f</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'y</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">f </span><span class="opn">(</span><span class="pln">g </span><span class="lit">'x</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">f </span><span class="opn">(</span><span class="pln">g </span><span class="lit">'x</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'y</span><span class="clo">)</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e32"></a>Exercise 5.32:</strong> Using the <code>preserving</code>
mechanism, the compiler will avoid saving and restoring <code>env</code> around the
evaluation of the operator of a combination in the case where the operator is a
symbol.  We could also build such optimizations into the evaluator.  Indeed,
the explicit-control evaluator of <a href="5_002e4.xhtml#g_t5_002e4">5.4</a> already performs a similar
optimization, by treating combinations with no operands as a special case.
</p>
<ol>
<li> Extend the explicit-control evaluator to recognize as a separate class of
expressions combinations whose operator is a symbol, and to take advantage of
this fact in evaluating such expressions.

</li><li> Alyssa P. Hacker suggests that by extending the evaluator to recognize more and
more special cases we could incorporate all the compiler’s optimizations, and
that this would eliminate the advantage of compilation altogether.  What do you
think of this idea?

</li></ol>
</blockquote>

<a id="g_t5_002e5_002e2"></a>
<a id="Compiling-Expressions"></a>
<h4 class="subsection"><span class="secnum">5.5.2</span><span class="sectitle">Compiling Expressions</span></h4>

<p>In this section and the next we implement the code generators to which the
<code>compile</code> procedure dispatches.
</p>
<a id="Compiling-linkage-code"></a>
<h5 class="subsubheading">Compiling linkage code</h5>

<p>In general, the output of each code generator will end with
instructions—generated by the procedure <code>compile-linkage</code>—that
implement the required linkage.  If the linkage is <code>return</code> then we must
generate the instruction <code>(goto (reg continue))</code>.  This needs the
<code>continue</code> register and does not modify any registers.  If the linkage is
<code>next</code>, then we needn’t include any additional instructions.  Otherwise,
the linkage is a label, and we generate a <code>goto</code> to that label, an
instruction that does not need or modify any registers.<a class="footnote_link" id="DOCF321" href="#FOOT321"><sup>321</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-linkage linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'return</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
          </span><span class="lit">'</span><span class="opn">(</span><span class="pln">continue</span><span class="clo">)</span><span class="pln">
          </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
          </span><span class="lit">'</span><span class="opn">((</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">)))))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'next</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">empty-instruction-sequence</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-instruction-sequence </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
          </span><span class="pun">`</span><span class="opn">((</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">linkage</span><span class="clo">)))))))</span></pre></div>

<p>The linkage code is appended to an instruction sequence by <code>preserving</code>
the <code>continue</code> register, since a <code>return</code> linkage will require the
<code>continue</code> register: If the given instruction sequence modifies
<code>continue</code> and the linkage code needs it, <code>continue</code> will be saved
and restored.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">end-with-linkage 
         linkage instruction-sequence</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">preserving </span><span class="lit">'</span><span class="opn">(</span><span class="pln">continue</span><span class="clo">)</span><span class="pln">
   instruction-sequence
   </span><span class="opn">(</span><span class="pln">compile-linkage linkage</span><span class="clo">)))</span></pre></div>

<a id="Compiling-simple-expressions"></a>
<h5 class="subsubheading">Compiling simple expressions</h5>

<p>The code generators for self-evaluating expressions, quotations, and variables
construct instruction sequences that assign the required value to the target
register and then proceed as specified by the linkage descriptor.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-self-evaluating 
         exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">end-with-linkage
   linkage </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
            </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">list target</span><span class="clo">)</span><span class="pln">
            </span><span class="pun">`</span><span class="opn">((</span><span class="pln">assign </span><span class="pun">,</span><span class="pln">target </span><span class="opn">(</span><span class="pln">const </span><span class="pun">,</span><span class="pln">exp</span><span class="clo">))))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-quoted exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">end-with-linkage
   linkage
   </span><span class="opn">(</span><span class="pln">make-instruction-sequence
    </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">list target</span><span class="clo">)</span><span class="pln">
    </span><span class="pun">`</span><span class="opn">((</span><span class="pln">assign 
       </span><span class="pun">,</span><span class="pln">target
       </span><span class="opn">(</span><span class="pln">const </span><span class="pun">,</span><span class="opn">(</span><span class="pln">text-of-quotation exp</span><span class="clo">)))))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-variable
         exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">end-with-linkage 
   linkage
   </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
    </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">list target</span><span class="clo">)</span><span class="pln">
    </span><span class="pun">`</span><span class="opn">((</span><span class="pln">assign </span><span class="pun">,</span><span class="pln">target
              </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">const </span><span class="pun">,</span><span class="pln">exp</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))))))</span></pre></div>

<p>All these assignment instructions modify the target register, and the one that
looks up a variable needs the <code>env</code> register.
</p>
<p>Assignments and definitions are handled much as they are in the interpreter.
We recursively generate code that computes the value to be assigned to the
variable, and append to it a two-instruction sequence that actually sets or
defines the variable and assigns the value of the whole expression (the symbol
<code>ok</code>) to the target register.  The recursive compilation has target
<code>val</code> and linkage <code>next</code> so that the code will put its result into
<code>val</code> and continue with the code that is appended after it.  The appending
is done preserving <code>env</code>, since the environment is needed for setting or
defining the variable and the code for the variable value could be the
compilation of a complex expression that might modify the registers in
arbitrary ways.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-assignment 
         exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">var </span><span class="opn">(</span><span class="pln">assignment-variable exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">get-value-code
         </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">assignment-value exp</span><span class="clo">)</span><span class="pln"> 
                  </span><span class="lit">'val</span><span class="pln">
                  </span><span class="lit">'next</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">end-with-linkage 
     linkage
     </span><span class="opn">(</span><span class="pln">preserving 
      </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
      get-value-code
      </span><span class="opn">(</span><span class="pln">make-instruction-sequence
       </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env val</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">list target</span><span class="clo">)</span><span class="pln">
       </span><span class="pun">`</span><span class="opn">((</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op set-variable-value!</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">const </span><span class="pun">,</span><span class="pln">var</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">assign </span><span class="pun">,</span><span class="pln">target </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))))))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-definition 
         exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">var </span><span class="opn">(</span><span class="pln">definition-variable exp</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">get-value-code
         </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">definition-value exp</span><span class="clo">)</span><span class="pln">
                  </span><span class="lit">'val</span><span class="pln">
                  </span><span class="lit">'next</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">end-with-linkage
     linkage
     </span><span class="opn">(</span><span class="pln">preserving 
      </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
      get-value-code
      </span><span class="opn">(</span><span class="pln">make-instruction-sequence
       </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env val</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">list target</span><span class="clo">)</span><span class="pln">
       </span><span class="pun">`</span><span class="opn">((</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op define-variable!</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">const </span><span class="pun">,</span><span class="pln">var</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">assign </span><span class="pun">,</span><span class="pln">target </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))))))))</span></pre></div>

<p>The appended two-instruction sequence requires <code>env</code> and <code>val</code> and
modifies the target.  Note that although we preserve <code>env</code> for this
sequence, we do not preserve <code>val</code>, because the <code>get-value-code</code> is
designed to explicitly place its result in <code>val</code> for use by this sequence.
(In fact, if we did preserve <code>val</code>, we would have a bug, because this
would cause the previous contents of <code>val</code> to be restored right after the
<code>get-value-code</code> is run.)
</p>
<a id="Compiling-conditional-expressions"></a>
<h5 class="subsubheading">Compiling conditional expressions</h5>

<p>The code for an <code>if</code> expression compiled with a given target and linkage
has the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="pln">compilation of predicate</span><span class="pun">,</span><span class="pln"> 
 target </span><code><span class="pln">val</span></code><span class="pun">,</span><span class="pln"> linkage </span><code><span class="pln">next</span></code></em><span class="pln">⟩
 </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op false?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label false-branch</span><span class="clo">))</span><span class="pln">
true-branch
 ⟨</span><em><span class="pln">compilation of consequent with given 
  target </span><span class="kwd">and</span><span class="pln"> given linkage </span><span class="kwd">or</span><span class="pln"> </span><code><span class="pln">after-if</span></code></em><span class="pln">⟩
false-branch
 ⟨</span><em><span class="pln">compilation of alternative 
  with given target </span><span class="kwd">and</span><span class="pln"> linkage</span></em><span class="pln">⟩
after-if</span></pre></div>

<p>To generate this code, we compile the predicate, consequent, and alternative,
and combine the resulting code with instructions to test the predicate result
and with newly generated labels to mark the true and false branches and the end
of the conditional.<a class="footnote_link" id="DOCF322" href="#FOOT322"><sup>322</sup></a> In this arrangement of code, we must branch around the true branch if the
test is false.  The only slight complication is in how the linkage for the true
branch should be handled.  If the linkage for the conditional is <code>return</code>
or a label, then the true and false branches will both use this same linkage.
If the linkage is <code>next</code>, the true branch ends with a jump around the code
for the false branch to the label at the end of the conditional.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-if exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">t-branch </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'true-branch</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">f-branch </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'false-branch</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">after-if </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'after-if</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">consequent-linkage
           </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'next</span><span class="clo">)</span><span class="pln"> 
               after-if
               linkage</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">p-code 
             </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">if-predicate exp</span><span class="clo">)</span><span class="pln">
                      </span><span class="lit">'val</span><span class="pln">
                      </span><span class="lit">'next</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">c-code
             </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">if-consequent exp</span><span class="clo">)</span><span class="pln"> 
                      target 
                      consequent-linkage</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">a-code
             </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">if-alternative exp</span><span class="clo">)</span><span class="pln">
                      target
                      linkage</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">preserving 
         </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env continue</span><span class="clo">)</span><span class="pln">
         p-code
         </span><span class="opn">(</span><span class="pln">append-instruction-sequences
          </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
           </span><span class="lit">'</span><span class="opn">(</span><span class="pln">val</span><span class="clo">)</span><span class="pln"> 
           </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
           </span><span class="pun">`</span><span class="opn">((</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op false?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">f-branch</span><span class="clo">))))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">parallel-instruction-sequences
           </span><span class="opn">(</span><span class="pln">append-instruction-sequences 
            t-branch c-code</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">append-instruction-sequences
            f-branch a-code</span><span class="clo">))</span><span class="pln">
          after-if</span><span class="clo">))))))</span></pre></div>

<p><code>Env</code> is preserved around the predicate code because it could be needed by
the true and false branches, and <code>continue</code> is preserved because it could
be needed by the linkage code in those branches.  The code for the true and
false branches (which are not executed sequentially) is appended using a
special combiner <code>parallel-instruction-sequences</code> described in 
<a href="#g_t5_002e5_002e4">5.5.4</a>.
</p>
<p>Note that <code>cond</code> is a derived expression, so all that the compiler needs
to do handle it is to apply the <code>cond-&gt;if</code> transformer (from 
<a href="4_002e1.xhtml#g_t4_002e1_002e2">4.1.2</a>) and compile the resulting <code>if</code> expression.
</p>
<a id="Compiling-sequences"></a>
<h5 class="subsubheading">Compiling sequences</h5>

<p>The compilation of sequences (from procedure bodies or explicit <code>begin</code>
expressions) parallels their evaluation.  Each expression of the sequence is
compiled—the last expression with the linkage specified for the sequence, and
the other expressions with linkage <code>next</code> (to execute the rest of the
sequence).  The instruction sequences for the individual expressions are
appended to form a single instruction sequence, such that <code>env</code> (needed
for the rest of the sequence) and <code>continue</code> (possibly needed for the
linkage at the end of the sequence) are preserved.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-sequence seq target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">last-exp? seq</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">first-exp seq</span><span class="clo">)</span><span class="pln"> target linkage</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">preserving </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env continue</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">first-exp seq</span><span class="clo">)</span><span class="pln"> target </span><span class="lit">'next</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">compile-sequence </span><span class="opn">(</span><span class="pln">rest-exps seq</span><span class="clo">)</span><span class="pln">
                         target
                         linkage</span><span class="clo">))))</span></pre></div>

<a id="Compiling-lambda-expressions"></a>
<h5 class="subsubheading">Compiling <code>lambda</code> expressions</h5>

<p><code>Lambda</code> expressions construct procedures.  The object code for a
<code>lambda</code> expression must have the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="pln">construct procedure object 
 </span><span class="kwd">and</span><span class="pln"> assign it to target register</span></em><span class="pln">⟩
⟨</span><var><span class="pln">linkage</span></var><span class="pln">⟩</span></pre></div>

<p>When we compile the <code>lambda</code> expression, we also generate the code for the
procedure body.  Although the body won’t be executed at the time of procedure
construction, it is convenient to insert it into the object code right after
the code for the <code>lambda</code>.  If the linkage for the <code>lambda</code>
expression is a label or <code>return</code>, this is fine.  But if the linkage is
<code>next</code>, we will need to skip around the code for the procedure body by
using a linkage that jumps to a label that is inserted after the body.  The
object code thus has the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="pln">construct procedure object 
 </span><span class="kwd">and</span><span class="pln"> assign it to target register</span></em><span class="pln">⟩
 ⟨</span><em><span class="pln">code for given linkage</span></em><span class="pln">⟩ </span><em><span class="kwd">or</span></em><span class="pln"> 
  </span><code><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label after-lambda</span><span class="clo">))</span></code><span class="pln">
 ⟨</span><em><span class="pln">compilation of procedure body</span></em><span class="pln">⟩
after-lambda</span></pre></div>

<p><code>Compile-lambda</code> generates the code for constructing the procedure object
followed by the code for the procedure body.  The procedure object will be
constructed at run time by combining the current environment (the environment
at the point of definition) with the entry point to the compiled procedure body
(a newly generated label).<a class="footnote_link" id="DOCF323" href="#FOOT323"><sup>323</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-lambda exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">proc-entry 
         </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'entry</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">after-lambda 
         </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'after-lambda</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">lambda-linkage
           </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'next</span><span class="clo">)</span><span class="pln">
               after-lambda
               linkage</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">append-instruction-sequences
       </span><span class="opn">(</span><span class="pln">tack-on-instruction-sequence
        </span><span class="opn">(</span><span class="pln">end-with-linkage 
         lambda-linkage
         </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
          </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">list target</span><span class="clo">)</span><span class="pln">
          </span><span class="pun">`</span><span class="opn">((</span><span class="pln">assign 
             </span><span class="pun">,</span><span class="pln">target
             </span><span class="opn">(</span><span class="pln">op make-compiled-procedure</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">proc-entry</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">)))))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">compile-lambda-body exp proc-entry</span><span class="clo">))</span><span class="pln">
       after-lambda</span><span class="clo">))))</span></pre></div>

<p><code>Compile-lambda</code> uses the special combiner
<code>tack-on-instruction-sequence</code> rather than
<code>append-instruction-sequences</code> (<a href="#g_t5_002e5_002e4">5.5.4</a>) to append the procedure body to the
<code>lambda</code> expression code, because the body is not part of the sequence of
instructions that will be executed when the combined sequence is entered;
rather, it is in the sequence only because that was a convenient place to put
it.
</p>
<p><code>Compile-lambda-body</code> constructs the code for the body of the procedure.
This code begins with a label for the entry point.  Next come instructions that
will cause the run-time evaluation environment to switch to the correct
environment for evaluating the procedure body—namely, the definition
environment of the procedure, extended to include the bindings of the formal
parameters to the arguments with which the procedure is called.  After this
comes the code for the sequence of expressions that makes up the procedure
body.  The sequence is compiled with linkage <code>return</code> and target
<code>val</code> so that it will end by returning from the procedure with the
procedure result in <code>val</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-lambda-body exp proc-entry</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">formals </span><span class="opn">(</span><span class="pln">lambda-parameters exp</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">append-instruction-sequences
     </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
      </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env proc argl</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
      </span><span class="pun">`</span><span class="opn">(</span><span class="pun">,</span><span class="pln">proc-entry
        </span><span class="opn">(</span><span class="pln">assign env 
                </span><span class="opn">(</span><span class="pln">op compiled-procedure-env</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">assign env
                </span><span class="opn">(</span><span class="pln">op extend-environment</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">const </span><span class="pun">,</span><span class="pln">formals</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">compile-sequence </span><span class="opn">(</span><span class="pln">lambda-body exp</span><span class="clo">)</span><span class="pln">
                       </span><span class="lit">'val</span><span class="pln">
                       </span><span class="lit">'return</span><span class="clo">))))</span></pre></div>

<a id="g_t5_002e5_002e3"></a>
<a id="Compiling-Combinations"></a>
<h4 class="subsection"><span class="secnum">5.5.3</span><span class="sectitle">Compiling Combinations</span></h4>

<p>The essence of the compilation process is the compilation of procedure
applications.  The code for a combination compiled with a given target and
linkage has the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="pln">compilation of operator</span><span class="pun">,</span><span class="pln"> 
 target </span><code><span class="pln">proc</span></code><span class="pun">,</span><span class="pln"> linkage </span><code><span class="pln">next</span></code></em><span class="pln">⟩
⟨</span><em><span class="pln">evaluate operands </span><span class="kwd">and</span><span class="pln"> construct 
 argument list in </span><code><span class="pln">argl</span></code></em><span class="pln">⟩
⟨</span><em><span class="pln">compilation of procedure call 
 with given target </span><span class="kwd">and</span><span class="pln"> linkage</span></em><span class="pln">⟩</span></pre></div>

<p>The registers <code>env</code>, <code>proc</code>, and <code>argl</code> may have to be saved and
restored during evaluation of the operator and operands.  Note that this is the
only place in the compiler where a target other than <code>val</code> is specified.
</p>
<p>The required code is generated by <code>compile-application</code>.  This recursively
compiles the operator, to produce code that puts the procedure to be applied
into <code>proc</code>, and compiles the operands, to produce code that evaluates the
individual operands of the application.  The instruction sequences for the
operands are combined (by <code>construct-arglist</code>) with code that constructs
the list of arguments in <code>argl</code>, and the resulting argument-list code is
combined with the procedure code and the code that performs the procedure call
(produced by <code>compile-procedure-call</code>).  In appending the code sequences,
the <code>env</code> register must be preserved around the evaluation of the operator
(since evaluating the operator might modify <code>env</code>, which will be needed to
evaluate the operands), and the <code>proc</code> register must be preserved around
the construction of the argument list (since evaluating the operands might
modify <code>proc</code>, which will be needed for the actual procedure application).
<code>Continue</code> must also be preserved throughout, since it is needed for the
linkage in the procedure call.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-application 
         exp target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">proc-code 
         </span><span class="opn">(</span><span class="pln">compile </span><span class="opn">(</span><span class="pln">operator exp</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'proc</span><span class="pln"> </span><span class="lit">'next</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">operand-codes
         </span><span class="opn">(</span><span class="pln">map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">operand</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">compile operand </span><span class="lit">'val</span><span class="pln"> </span><span class="lit">'next</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">operands exp</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">preserving 
     </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env continue</span><span class="clo">)</span><span class="pln">
     proc-code
     </span><span class="opn">(</span><span class="pln">preserving 
      </span><span class="lit">'</span><span class="opn">(</span><span class="pln">proc continue</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">construct-arglist operand-codes</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">compile-procedure-call 
       target
       linkage</span><span class="clo">)))))</span></pre></div>

<p>The code to construct the argument list will evaluate each operand into
<code>val</code> and then <code>cons</code> that value onto the argument list being
accumulated in <code>argl</code>.  Since we <code>cons</code> the arguments onto
<code>argl</code> in sequence, we must start with the last argument and end with the
first, so that the arguments will appear in order from first to last in the
resulting list.  Rather than waste an instruction by initializing <code>argl</code>
to the empty list to set up for this sequence of evaluations, we make the first
code sequence construct the initial <code>argl</code>.  The general form of the
argument-list construction is thus as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="pln">compilation of last operand</span><span class="pun">,</span><span class="pln"> targeted to </span><code><span class="pln">val</span></code></em><span class="pln">⟩
</span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
⟨</span><em><span class="pln">compilation of next operand</span><span class="pun">,</span><span class="pln"> targeted to </span><code><span class="pln">val</span></code></em><span class="pln">⟩
</span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
</span><span class="roman"><span class="pun">…</span></span><span class="pln">
⟨</span><em><span class="pln">compilation of first operand</span><span class="pun">,</span><span class="pln"> targeted to </span><code><span class="pln">val</span></code></em><span class="pln">⟩
</span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span></pre></div>

<p><code>Argl</code> must be preserved around each operand evaluation except the first
(so that arguments accumulated so far won’t be lost), and <code>env</code> must be
preserved around each operand evaluation except the last (for use by subsequent
operand evaluations).
</p>
<p>Compiling this argument code is a bit tricky, because of the special treatment
of the first operand to be evaluated and the need to preserve <code>argl</code> and
<code>env</code> in different places.  The <code>construct-arglist</code> procedure takes
as arguments the code that evaluates the individual operands.  If there are no
operands at all, it simply emits the instruction
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">const </span><span class="opn">(</span><span class="clo">)))</span></pre></div>

<p>Otherwise, <code>construct-arglist</code> creates code that initializes <code>argl</code>
with the last argument, and appends code that evaluates the rest of the
arguments and adjoins them to <code>argl</code> in succession.  In order to process
the arguments from last to first, we must reverse the list of operand code
sequences from the order supplied by <code>compile-application</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">construct-arglist operand-codes</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">operand-codes 
         </span><span class="opn">(</span><span class="pln">reverse operand-codes</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? operand-codes</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
         </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> 
         </span><span class="lit">'</span><span class="opn">(</span><span class="pln">argl</span><span class="clo">)</span><span class="pln">
         </span><span class="lit">'</span><span class="opn">((</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">const </span><span class="opn">(</span><span class="clo">)))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">code-to-get-last-arg
               </span><span class="opn">(</span><span class="pln">append-instruction-sequences
                </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> operand-codes</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
                 </span><span class="lit">'</span><span class="opn">(</span><span class="pln">val</span><span class="clo">)</span><span class="pln">
                 </span><span class="lit">'</span><span class="opn">(</span><span class="pln">argl</span><span class="clo">)</span><span class="pln">
                 </span><span class="lit">'</span><span class="opn">((</span><span class="pln">assign argl
                           </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln">
                           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)))))))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> operand-codes</span><span class="clo">))</span><span class="pln">
              code-to-get-last-arg
              </span><span class="opn">(</span><span class="pln">preserving 
               </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
               code-to-get-last-arg
               </span><span class="opn">(</span><span class="pln">code-to-get-rest-args
                </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> operand-codes</span><span class="clo">))))))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">code-to-get-rest-args operand-codes</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">code-for-next-arg
         </span><span class="opn">(</span><span class="pln">preserving 
          </span><span class="lit">'</span><span class="opn">(</span><span class="pln">argl</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> operand-codes</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
           </span><span class="lit">'</span><span class="opn">(</span><span class="pln">val argl</span><span class="clo">)</span><span class="pln">
           </span><span class="lit">'</span><span class="opn">(</span><span class="pln">argl</span><span class="clo">)</span><span class="pln">
           </span><span class="lit">'</span><span class="opn">((</span><span class="pln">assign argl
                     </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">)))))))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> operand-codes</span><span class="clo">))</span><span class="pln">
        code-for-next-arg
        </span><span class="opn">(</span><span class="pln">preserving 
         </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env</span><span class="clo">)</span><span class="pln">
         code-for-next-arg
         </span><span class="opn">(</span><span class="pln">code-to-get-rest-args 
          </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> operand-codes</span><span class="clo">))))))</span></pre></div>

<a id="Applying-procedures"></a>
<h5 class="subsubheading">Applying procedures</h5>

<p>After evaluating the elements of a combination, the compiled code must apply
the procedure in <code>proc</code> to the arguments in <code>argl</code>.  The code
performs essentially the same dispatch as the <code>apply</code> procedure in the
metacircular evaluator of <a href="4_002e1.xhtml#g_t4_002e1_002e1">4.1.1</a> or the <code>apply-dispatch</code>
entry point in the explicit-control evaluator of <a href="5_002e4.xhtml#g_t5_002e4_002e1">5.4.1</a>.  It
checks whether the procedure to be applied is a primitive procedure or a
compiled procedure.  For a primitive procedure, it uses
<code>apply-primitive-procedure</code>; we will see shortly how it handles compiled
procedures.  The procedure-application code has the following form:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch</span><span class="clo">))</span><span class="pln">
compiled-branch
 ⟨</span><em><span class="pln">code to apply compiled procedure 
  with given target </span><span class="kwd">and</span><span class="pln"> appropriate linkage</span></em><span class="pln">⟩
primitive-branch
 </span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">target</span></var><span class="pln">⟩
         </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
 ⟨</span><var><span class="pln">linkage</span></var><span class="pln">⟩
after-call</span></pre></div>

<p>Observe that the compiled branch must skip around the primitive branch.
Therefore, if the linkage for the original procedure call was <code>next</code>, the
compound branch must use a linkage that jumps to a label that is inserted after
the primitive branch.  (This is similar to the linkage used for the true branch
in <code>compile-if</code>.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-procedure-call
         target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">primitive-branch 
         </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'primitive-branch</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">compiled-branch 
         </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'compiled-branch</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">after-call
         </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'after-call</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">compiled-linkage
           </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'next</span><span class="clo">)</span><span class="pln">
               after-call
               linkage</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">append-instruction-sequences
       </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
        </span><span class="lit">'</span><span class="opn">(</span><span class="pln">proc</span><span class="clo">)</span><span class="pln">
        </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln">
        </span><span class="pun">`</span><span class="opn">((</span><span class="pln">test 
           </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">branch 
           </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">primitive-branch</span><span class="clo">))))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">parallel-instruction-sequences
        </span><span class="opn">(</span><span class="pln">append-instruction-sequences
         compiled-branch
         </span><span class="opn">(</span><span class="pln">compile-proc-appl 
          target
          compiled-linkage</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">append-instruction-sequences
         primitive-branch
         </span><span class="opn">(</span><span class="pln">end-with-linkage
          linkage
          </span><span class="opn">(</span><span class="pln">make-instruction-sequence
           </span><span class="lit">'</span><span class="opn">(</span><span class="pln">proc argl</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">list target</span><span class="clo">)</span><span class="pln">
           </span><span class="pun">`</span><span class="opn">((</span><span class="pln">assign 
              </span><span class="pun">,</span><span class="pln">target
              </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">)))))))</span><span class="pln">
       after-call</span><span class="clo">))))</span></pre></div>

<p>The primitive and compound branches, like the true and false branches in
<code>compile-if</code>, are appended using <code>parallel-instruction-sequences</code>
rather than the ordinary <code>append-instruction-sequences</code>, because they will
not be executed sequentially.
</p>
<a id="Applying-compiled-procedures"></a>
<h5 class="subsubheading">Applying compiled procedures</h5>

<p>The code that handles procedure application is the most subtle part of the
compiler, even though the instruction sequences it generates are very short.  A
compiled procedure (as constructed by <code>compile-lambda</code>) has an entry
point, which is a label that designates where the code for the procedure
starts.  The code at this entry point computes a result in <code>val</code> and
returns by executing the instruction <code>(goto (reg continue))</code>.  Thus, we
might expect the code for a compiled-procedure application (to be generated by
<code>compile-proc-appl</code>) with a given target and linkage to look like this if
the linkage is a label
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign continue 
        </span><span class="opn">(</span><span class="pln">label proc-return</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign val
         </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
proc-return
 </span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">target</span></var><span class="pln">⟩ 
         </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">   </span><span class="roman"><span class="com">; included if target is not </span><code><span class="com">val</span></code></span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label ⟨</span><var><span class="pln">linkage</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">   </span><span class="roman"><span class="com">; linkage code</span></span>
</pre></div>

<p>or like this if the linkage is <code>return</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign continue 
         </span><span class="opn">(</span><span class="pln">label proc-return</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign val 
         </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
proc-return
 </span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">target</span></var><span class="pln">⟩
         </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">   </span><span class="roman"><span class="com">; included if target is not </span><code><span class="com">val</span></code></span><span class="pln">
 </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">   </span><span class="roman"><span class="com">; linkage code</span></span>
</pre></div>

<p>This code sets up <code>continue</code> so that the procedure will return to a label
<code>proc-return</code> and jumps to the procedure’s entry point.  The code at
<code>proc-return</code> transfers the procedure’s result from <code>val</code> to the
target register (if necessary) and then jumps to the location specified by the
linkage.  (The linkage is always <code>return</code> or a label, because
<code>compile-procedure-call</code> replaces a <code>next</code> linkage for the
compound-procedure branch by an <code>after-call</code> label.)
</p>
<p>In fact, if the target is not <code>val</code>, that is exactly the code our compiler
will generate.<a class="footnote_link" id="DOCF324" href="#FOOT324"><sup>324</sup></a>  Usually, however, the target is
<code>val</code> (the only time the compiler specifies a different register is when
targeting the evaluation of an operator to <code>proc</code>), so the procedure
result is put directly into the target register and there is no need to return
to a special location that copies it.  Instead, we simplify the code by setting
up <code>continue</code> so that the procedure will “return” directly to the place
specified by the caller’s linkage:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="kwd">set</span><span class="pln"> up </span><code><span class="pln">continue</span></code><span class="pln"> for linkage</span></em><span class="pln">⟩
</span><span class="opn">(</span><span class="pln">assign val 
        </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span></pre></div>

<p>If the linkage is a label, we set up <code>continue</code> so that the procedure will
return to that label.  (That is, the <code>(goto (reg continue))</code> the procedure
ends with becomes equivalent to the <code>(goto (label ⟨<var>linkage</var>⟩))</code> at
<code>proc-return</code> above.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign continue 
        </span><span class="opn">(</span><span class="pln">label ⟨</span><var><span class="pln">linkage</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign val
        </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span></pre></div>

<p>If the linkage is <code>return</code>, we don’t need to set up <code>continue</code> at
all: It already holds the desired location.  (That is, the <code>(goto (reg
continue))</code> the procedure ends with goes directly to the place where the
<code>(goto (reg continue))</code> at <code>proc-return</code> would have gone.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign val
        </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span></pre></div>

<p>With this implementation of the <code>return</code> linkage, the compiler generates
tail-recursive code.  Calling a procedure as the final step in a procedure body
does a direct transfer, without saving any information on the stack.
</p>
<p>Suppose instead that we had handled the case of a procedure call with a linkage
of <code>return</code> and a target of <code>val</code> as shown above for a non-<code>val</code>
target.  This would destroy tail recursion.  Our system would still give the
same value for any expression.  But each time we called a procedure, we would
save <code>continue</code> and return after the call to undo the (useless) save.
These extra saves would accumulate during a nest of procedure
calls.<a class="footnote_link" id="DOCF325" href="#FOOT325"><sup>325</sup></a>
</p>
<p><code>Compile-proc-appl</code> generates the above procedure-application code by
considering four cases, depending on whether the target for the call is
<code>val</code> and whether the linkage is <code>return</code>.  Observe that the
instruction sequences are declared to modify all the registers, since executing
the procedure body can change the registers in arbitrary ways.<a class="footnote_link" id="DOCF326" href="#FOOT326"><sup>326</sup></a>
Also note that the code sequence for the case with target <code>val</code> and
linkage <code>return</code> is declared to need <code>continue</code>: Even though
<code>continue</code> is not explicitly used in the two-instruction sequence, we must
be sure that <code>continue</code> will have the correct value when we enter the
compiled procedure.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-proc-appl target linkage</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> target </span><span class="lit">'val</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'return</span><span class="clo">)))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
          </span><span class="lit">'</span><span class="opn">(</span><span class="pln">proc</span><span class="clo">)</span><span class="pln">
          all-regs
          </span><span class="pun">`</span><span class="opn">((</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">linkage</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">assign 
             val 
             </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)))))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> target </span><span class="lit">'val</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'return</span><span class="clo">)))</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">proc-return 
                </span><span class="opn">(</span><span class="pln">make-label </span><span class="lit">'proc-return</span><span class="clo">)))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
            </span><span class="lit">'</span><span class="opn">(</span><span class="pln">proc</span><span class="clo">)</span><span class="pln">
            all-regs
            </span><span class="pun">`</span><span class="opn">((</span><span class="pln">assign continue 
                      </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">proc-return</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">assign 
               val 
               </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
              </span><span class="pun">,</span><span class="pln">proc-return
              </span><span class="opn">(</span><span class="pln">assign </span><span class="pun">,</span><span class="pln">target </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">linkage</span><span class="clo">))))))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> target </span><span class="lit">'val</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'return</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">make-instruction-sequence 
          </span><span class="lit">'</span><span class="opn">(</span><span class="pln">proc continue</span><span class="clo">)</span><span class="pln"> 
          all-regs
          </span><span class="lit">'</span><span class="opn">((</span><span class="pln">assign 
             val 
             </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)))))</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> target </span><span class="lit">'val</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> linkage </span><span class="lit">'return</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"return linkage, 
                 target not val: COMPILE"</span><span class="pln">
                target</span><span class="clo">))))</span></pre></div>

<a id="g_t5_002e5_002e4"></a>
<a id="Combining-Instruction-Sequences"></a>
<h4 class="subsection"><span class="secnum">5.5.4</span><span class="sectitle">Combining Instruction Sequences</span></h4>

<p>This section describes the details on how instruction sequences are represented
and combined.  Recall from <a href="#g_t5_002e5_002e1">5.5.1</a> that an instruction sequence is
represented as a list of the registers needed, the registers modified, and the
actual instructions.  We will also consider a label (symbol) to be a degenerate
case of an instruction sequence, which doesn’t need or modify any registers.
So to determine the registers needed and modified by instruction sequences we
use the selectors
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">registers-needed s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? s</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">registers-modified s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? s</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> s</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">statements s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">symbol? s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> s</span><span class="clo">)))</span></pre></div>

<p>and to determine whether a given
sequence needs or modifies a given register we use the predicates
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">needs-register? seq reg</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">memq reg </span><span class="opn">(</span><span class="pln">registers-needed seq</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">modifies-register? seq reg</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">memq reg </span><span class="opn">(</span><span class="pln">registers-modified seq</span><span class="clo">)))</span></pre></div>

<p>In terms of these predicates and selectors, we can implement the various
instruction sequence combiners used throughout the compiler.
</p>
<p>The basic combiner is <code>append-instruction-sequences</code>.  This takes as
arguments an arbitrary number of instruction sequences that are to be executed
sequentially and returns an instruction sequence whose statements are the
statements of all the sequences appended together.  The subtle point is to
determine the registers that are needed and modified by the resulting sequence.
It modifies those registers that are modified by any of the sequences; it needs
those registers that must be initialized before the first sequence can be run
(the registers needed by the first sequence), together with those registers
needed by any of the other sequences that are not initialized (modified) by
sequences preceding it.
</p>
<p>The sequences are appended two at a time by <code>append-2-sequences</code>.  This
takes two instruction sequences <code>seq1</code> and <code>seq2</code> and returns the
instruction sequence whose statements are the statements of <code>seq1</code>
followed by the statements of <code>seq2</code>, whose modified registers are those
registers that are modified by either <code>seq1</code> or <code>seq2</code>, and whose
needed registers are the registers needed by <code>seq1</code> together with those
registers needed by <code>seq2</code> that are not modified by <code>seq1</code>.  (In
terms of set operations, the new set of needed registers is the union of the
set of registers needed by <code>seq1</code> with the set difference of the registers
needed by <code>seq2</code> and the registers modified by <code>seq1</code>.)  Thus,
<code>append-instruction-sequences</code> is implemented as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append-instruction-sequences </span><span class="pun">.</span><span class="pln"> seqs</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append-2-sequences seq1 seq2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-instruction-sequence
     </span><span class="opn">(</span><span class="pln">list-union 
      </span><span class="opn">(</span><span class="pln">registers-needed seq1</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">list-difference 
       </span><span class="opn">(</span><span class="pln">registers-needed seq2</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">registers-modified seq1</span><span class="clo">)))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">list-union
      </span><span class="opn">(</span><span class="pln">registers-modified seq1</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">registers-modified seq2</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="pln">statements seq1</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">statements seq2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append-seq-list seqs</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? seqs</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">empty-instruction-sequence</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">append-2-sequences 
         </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> seqs</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">append-seq-list </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> seqs</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">append-seq-list seqs</span><span class="clo">))</span></pre></div>

<p>This procedure uses some simple operations for manipulating sets represented as
lists, similar to the (unordered) set representation described in 
<a href="2_002e3.xhtml#g_t2_002e3_002e3">2.3.3</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list-union s1 s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">memq </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">list-union </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">list-union </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">list-difference s1 s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">null? s1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">memq </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">list-difference </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">list-difference </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln">
                                s2</span><span class="clo">)))))</span></pre></div>

<p><code>Preserving</code>, the second major instruction sequence combiner, takes a list
of registers <code>regs</code> and two instruction sequences <code>seq1</code> and
<code>seq2</code> that are to be executed sequentially.  It returns an instruction
sequence whose statements are the statements of <code>seq1</code> followed by the
statements of <code>seq2</code>, with appropriate <code>save</code> and <code>restore</code>
instructions around <code>seq1</code> to protect the registers in <code>regs</code> that
are modified by <code>seq1</code> but needed by <code>seq2</code>.  To accomplish this,
<code>preserving</code> first creates a sequence that has the required <code>save</code>s
followed by the statements of <code>seq1</code> followed by the required
<code>restore</code>s.  This sequence needs the registers being saved and restored in
addition to the registers needed by <code>seq1</code>, and modifies the registers
modified by <code>seq1</code> except for the ones being saved and restored.  This
augmented sequence and <code>seq2</code> are then appended in the usual way.  The
following procedure implements this strategy recursively, walking down the list
of registers to be preserved:<a class="footnote_link" id="DOCF327" href="#FOOT327"><sup>327</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">preserving regs seq1 seq2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? regs</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">append-instruction-sequences seq1 seq2</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">first-reg </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> regs</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">and</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">needs-register? seq2 first-reg</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">modifies-register? seq1 
                                 first-reg</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">preserving 
             </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> regs</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">make-instruction-sequence
              </span><span class="opn">(</span><span class="pln">list-union 
               </span><span class="opn">(</span><span class="pln">list first-reg</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">registers-needed seq1</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">list-difference
               </span><span class="opn">(</span><span class="pln">registers-modified seq1</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">list first-reg</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">append </span><span class="pun">`</span><span class="opn">((</span><span class="pln">save </span><span class="pun">,</span><span class="pln">first-reg</span><span class="clo">))</span><span class="pln">
                      </span><span class="opn">(</span><span class="pln">statements seq1</span><span class="clo">)</span><span class="pln">
                      </span><span class="pun">`</span><span class="opn">((</span><span class="pln">restore </span><span class="pun">,</span><span class="pln">first-reg</span><span class="clo">))))</span><span class="pln">
             seq2</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">preserving 
             </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> regs</span><span class="clo">)</span><span class="pln">
             seq1
             seq2</span><span class="clo">)))))</span></pre></div>

<p>Another sequence combiner, <code>tack-on-instruction-sequence</code>, is used by
<code>compile-lambda</code> to append a procedure body to another sequence.  Because
the procedure body is not “in line” to be executed as part of the combined
sequence, its register use has no impact on the register use of the sequence in
which it is embedded.  We thus ignore the procedure body’s sets of needed and
modified registers when we tack it onto the other sequence.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tack-on-instruction-sequence 
         seq body-seq</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">make-instruction-sequence
   </span><span class="opn">(</span><span class="pln">registers-needed seq</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">registers-modified seq</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="pln">statements seq</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">statements body-seq</span><span class="clo">))))</span></pre></div>

<p><code>Compile-if</code> and <code>compile-procedure-call</code> use a special combiner
called <code>parallel-instruction-sequences</code> to append the two alternative
branches that follow a test.  The two branches will never be executed
sequentially; for any particular evaluation of the test, one branch or the
other will be entered.  Because of this, the registers needed by the second
branch are still needed by the combined sequence, even if these are modified by
the first branch.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">parallel-instruction-sequences 
         seq1 seq2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">make-instruction-sequence
   </span><span class="opn">(</span><span class="pln">list-union </span><span class="opn">(</span><span class="pln">registers-needed seq1</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">registers-needed seq2</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">list-union </span><span class="opn">(</span><span class="pln">registers-modified seq1</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">registers-modified seq2</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="pln">statements seq1</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">statements seq2</span><span class="clo">))))</span></pre></div>

<a id="g_t5_002e5_002e5"></a>
<a id="An-Example-of-Compiled-Code"></a>
<h4 class="subsection"><span class="secnum">5.5.5</span><span class="sectitle">An Example of Compiled Code</span></h4>

<p>Now that we have seen all the elements of the compiler, let us examine an
example of compiled code to see how things fit together.  We will compile the
definition of a recursive <code>factorial</code> procedure by calling <code>compile</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">compile
 </span><span class="lit">'</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="lit">1</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">)))</span><span class="pln">
 </span><span class="lit">'val</span><span class="pln">
 </span><span class="lit">'next</span><span class="clo">)</span></pre></div>

<p>We have specified that the value of the <code>define</code> expression should be
placed in the <code>val</code> register.  We don’t care what the compiled code does
after executing the <code>define</code>, so our choice of <code>next</code> as the linkage
descriptor is arbitrary.
</p>
<p><code>Compile</code> determines that the expression is a definition, so it calls
<code>compile-definition</code> to compile code to compute the value to be assigned
(targeted to <code>val</code>), followed by code to install the definition, followed
by code to put the value of the <code>define</code> (which is the symbol <code>ok</code>)
into the target register, followed finally by the linkage code.  <code>Env</code> is
preserved around the computation of the value, because it is needed in order to
install the definition.  Because the linkage is <code>next</code>, there is no
linkage code in this case.  The skeleton of the compiled code is thus
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="pln">save </span><code><span class="pln">env</span></code><span class="pln"> </span><span class="kwd">if</span><span class="pln"> modified by code to compute value</span></em><span class="pln">⟩
  ⟨</span><em><span class="pln">compilation of definition value</span><span class="pun">,</span><span class="pln"> 
   target </span><code><span class="pln">val</span></code><span class="pun">,</span><span class="pln"> linkage </span><code><span class="pln">next</span></code></em><span class="pln">⟩
  ⟨</span><em><span class="pln">restore </span><code><span class="pln">env</span></code><span class="pln"> </span><span class="kwd">if</span><span class="pln"> saved above</span></em><span class="pln">⟩
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op define-variable!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const factorial</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))</span></pre></div>

<p>The expression that is to be compiled to produce the value for the variable
<code>factorial</code> is a <code>lambda</code> expression whose value is the procedure
that computes factorials.  <code>Compile</code> handles this by calling
<code>compile-lambda</code>, which compiles the procedure body, labels it as a new
entry point, and generates the instruction that will combine the procedure body
at the new entry point with the run-time environment and assign the result to
<code>val</code>.  The sequence then skips around the compiled procedure code, which
is inserted at this point.  The procedure code itself begins by extending the
procedure’s definition environment by a frame that binds the formal parameter
<code>n</code> to the procedure argument.  Then comes the actual procedure body.
Since this code for the value of the variable doesn’t modify the <code>env</code>
register, the optional <code>save</code> and <code>restore</code> shown above aren’t
generated.  (The procedure code at <code>entry2</code> isn’t executed at this point,
so its use of <code>env</code> is irrelevant.)  Therefore, the skeleton for the
compiled code becomes
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op make-compiled-procedure</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">label entry2</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label after-lambda1</span><span class="clo">))</span><span class="pln">
entry2
  </span><span class="opn">(</span><span class="pln">assign env </span><span class="opn">(</span><span class="pln">op compiled-procedure-env</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env </span><span class="opn">(</span><span class="pln">op extend-environment</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">const </span><span class="opn">(</span><span class="pln">n</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  ⟨</span><em><span class="pln">compilation of procedure body</span></em><span class="pln">⟩
after-lambda1
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op define-variable!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const factorial</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))</span></pre></div>

<p>A procedure body is always compiled (by <code>compile-lambda-body</code>) as a
sequence with target <code>val</code> and linkage <code>return</code>.  The sequence in
this case consists of a single <code>if</code> expression:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
    </span><span class="lit">1</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">))</span></pre></div>

<p><code>Compile-if</code> generates code that first computes the predicate (targeted to
<code>val</code>), then checks the result and branches around the true branch if the
predicate is false.  <code>Env</code> and <code>continue</code> are preserved around the
predicate code, since they may be needed for the rest of the <code>if</code>
expression.  Since the <code>if</code> expression is the final expression (and only
expression) in the sequence making up the procedure body, its target is
<code>val</code> and its linkage is <code>return</code>, so the true and false branches are
both compiled with target <code>val</code> and linkage <code>return</code>.  (That is, the
value of the conditional, which is the value computed by either of its
branches, is the value of the procedure.)
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">⟨</span><em><span class="pln">save </span><code><span class="pln">continue</span></code><span class="pun">,</span><span class="pln"> </span><code><span class="pln">env</span></code><span class="pln"> </span><span class="kwd">if</span><span class="pln"> modified by 
 predicate </span><span class="kwd">and</span><span class="pln"> needed by branches</span></em><span class="pln">⟩
  ⟨</span><em><span class="pln">compilation of predicate</span><span class="pun">,</span><span class="pln"> 
   target </span><code><span class="pln">val</span></code><span class="pun">,</span><span class="pln"> linkage </span><code><span class="pln">next</span></code></em><span class="pln">⟩
  ⟨</span><em><span class="pln">restore </span><code><span class="pln">continue</span></code><span class="pun">,</span><span class="pln"> </span><code><span class="pln">env</span></code><span class="pln"> </span><span class="kwd">if</span><span class="pln"> saved above</span></em><span class="pln">⟩
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op false?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label false-branch4</span><span class="clo">))</span><span class="pln">
true-branch5
  ⟨</span><em><span class="pln">compilation of true branch</span><span class="pun">,</span><span class="pln"> 
   target </span><code><span class="pln">val</span></code><span class="pun">,</span><span class="pln"> linkage </span><code><span class="pln">return</span></code></em><span class="pln">⟩
false-branch4
  ⟨</span><em><span class="pln">compilation of false branch</span><span class="pun">,</span><span class="pln"> 
   target </span><code><span class="pln">val</span></code><span class="pun">,</span><span class="pln"> linkage </span><code><span class="pln">return</span></code></em><span class="pln">⟩
after-if3</span></pre></div>

<p>The predicate <code>(= n 1)</code> is a procedure call.  This looks up the operator
(the symbol <code>=</code>) and places this value in <code>proc</code>.  It then assembles
the arguments <code>1</code> and the value of <code>n</code> into <code>argl</code>.  Then it
tests whether <code>proc</code> contains a primitive or a compound procedure, and
dispatches to a primitive branch or a compound branch accordingly.  Both
branches resume at the <code>after-call</code> label.  The requirements to preserve
registers around the evaluation of the operator and operands don’t result in
any saving of registers, because in this case those evaluations don’t modify
the registers in question.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">  </span><span class="opn">(</span><span class="pln">assign proc </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">const </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">const n</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch17</span><span class="clo">))</span><span class="pln">
compiled-branch16
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-call15</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch17
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
after-call15</span></pre></div>

<p>The true branch, which is the constant 1, compiles (with target <code>val</code> and
linkage <code>return</code>) to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span></pre></div>

<p>The code for the false branch is another procedure call, where the procedure
is the value of the symbol <code>*</code>, and the arguments are <code>n</code> and the
result of another procedure call (a call to <code>factorial</code>).  Each of these
calls sets up <code>proc</code> and <code>argl</code> and its own primitive and compound
branches.  <a href="#Figure-5_002e17">Figure 5.17</a> shows the complete compilation of the definition
of the <code>factorial</code> procedure.  Notice that the possible <code>save</code> and
<code>restore</code> of <code>continue</code> and <code>env</code> around the predicate, shown
above, are in fact generated, because these registers are modified by the
procedure call in the predicate and needed for the procedure call and the
<code>return</code> linkage in the branches.
</p>
<blockquote>
<p><strong><a id="Figure-5_002e17"></a>Figure 5.17:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> Compilation of the definition of the <code>factorial</code> procedure.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="roman"><span class="com">;; construct the procedure and skip over code</span></span><span class="pln">
</span><span class="roman"><span class="com">;; for the procedure body</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op make-compiled-procedure</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">label entry2</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label after-lambda1</span><span class="clo">))</span><span class="pln">
entry2     </span><span class="roman"><span class="com">; calls to </span><code><span class="com">factorial</span></code><span class="com"> will enter here</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env 
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-env</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env
          </span><span class="opn">(</span><span class="pln">op extend-environment</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const </span><span class="opn">(</span><span class="pln">n</span><span class="clo">))</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
</span><span class="roman"><span class="com">;; begin actual procedure body</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
</span><span class="roman"><span class="com">;; compute </span><code><span class="com">(= n 1)</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc 
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const n</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch17</span><span class="clo">))</span><span class="pln">
compiled-branch16
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-call15</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch17
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
after-call15   </span><span class="roman"><span class="com">; </span><code><span class="com">val</span></code><span class="com"> now contains result of </span><code><span class="com">(= n 1)</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op false?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label false-branch4</span><span class="clo">))</span><span class="pln">
true-branch5  </span><span class="roman"><span class="com">; return 1</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">

false-branch4
</span><span class="roman"><span class="com">;; compute and return </span><code><span class="com">(* (factorial (- n 1)) n)</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc 
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const </span><span class="pun">*</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save proc</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; save </span><code><span class="com">*</span></code></span><span class="com"> procedure</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const n</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save argl</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; save partial argument list for </span><code><span class="com">*</span></code></span><span class="pln">
</span><span class="roman"><span class="com">;; compute </span><code><span class="com">(factorial (- n 1))</span></code><span class="com">,</span></span><span class="com"> </span><span class="pln">
</span><span class="roman"><span class="com">;; which is the other argument for </span><code><span class="com">*</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const factorial</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save proc</span><span class="clo">)</span><span class="pln">  </span><span class="roman"><span class="com">; save </span><code><span class="com">factorial</span></code><span class="com"> procedure</span></span><span class="pln">
</span><span class="roman"><span class="com">;; compute </span><code><span class="com">(- n 1)</span></code><span class="com">, which is the argument for </span><code><span class="com">factorial</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc 
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">const </span><span class="pun">-</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const n</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch8</span><span class="clo">))</span><span class="pln">
compiled-branch7
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-call6</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch8
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">

after-call6   </span><span class="roman"><span class="com">; </span><code><span class="com">val</span></code><span class="com"> now contains result of </span><code><span class="com">(- n 1)</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore proc</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="com">; restore </span><code><span class="com">factorial</span></code></span><span class="pln">
</span><span class="roman"><span class="com">;; apply </span><code><span class="com">factorial</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch11</span><span class="clo">))</span><span class="pln">
compiled-branch10
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-call9</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch11
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
after-call9      </span><span class="roman"><span class="com">; </span><code><span class="com">val</span></code><span class="com"> now contains result</span></span><span class="com"> </span><span class="pln">
                 </span><span class="roman"><span class="com">; of </span><code><span class="com">(factorial (- n 1))</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore argl</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="com">; restore partial argument list for </span><code><span class="com">*</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore proc</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="com">; restore </span><code><span class="com">*</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
</span><span class="roman"><span class="com">;; apply </span><code><span class="com">*</span></code><span class="com"> and return its value</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch14</span><span class="clo">))</span><span class="pln">
compiled-branch13
</span><span class="roman"><span class="com">;; note that a compound procedure here</span></span><span class="pln">
</span><span class="roman"><span class="com">;; is called tail-recursively</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch14
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">
after-call12
after-if3
after-lambda1
</span><span class="roman"><span class="com">;; assign the procedure to the variable </span><code><span class="com">factorial</span></code></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op define-variable!</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">const factorial</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e33"></a>Exercise 5.33:</strong> Consider the following definition
of a factorial procedure, which is slightly different from the one given above:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial-alt n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> n </span><span class="opn">(</span><span class="pln">factorial-alt </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>Compile this procedure and compare the resulting code with that produced for
<code>factorial</code>.  Explain any differences you find.  Does either program
execute more efficiently than the other?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e34"></a>Exercise 5.34:</strong> Compile the iterative factorial
procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter product counter</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter n</span><span class="clo">)</span><span class="pln">
        product
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>Annotate the resulting code, showing the essential difference between the code
for iterative and recursive versions of <code>factorial</code> that makes one process
build up stack space and the other run in constant stack space.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e35"></a>Exercise 5.35:</strong> What expression was compiled to
produce the code shown in <a href="#Figure-5_002e18">Figure 5.18</a>?
</p></blockquote>

<blockquote>
<p><strong><a id="Figure-5_002e18"></a>Figure 5.18:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> An example of compiler output.  See
<a href="#Exercise-5_002e35">Exercise 5.35</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op make-compiled-procedure</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">label entry16</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label after-lambda15</span><span class="clo">))</span><span class="pln">
entry16
  </span><span class="opn">(</span><span class="pln">assign env </span><span class="opn">(</span><span class="pln">op compiled-procedure-env</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env </span><span class="opn">(</span><span class="pln">op extend-environment</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">const </span><span class="opn">(</span><span class="pln">x</span><span class="clo">))</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">const </span><span class="pun">+</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">save proc</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">const g</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">const </span><span class="pun">+</span><span class="clo">)</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const </span><span class="lit">2</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">const x</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch19</span><span class="clo">))</span><span class="pln">
compiled-branch18
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-call17</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch19
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
after-call17
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch22</span><span class="clo">))</span><span class="pln">
compiled-branch21
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-call20</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch22
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
after-call20
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">const x</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl
          </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">cons</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-branch25</span><span class="clo">))</span><span class="pln">
compiled-branch24
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
primitive-branch25
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln"> 
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">
after-call23
after-lambda15
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op define-variable!</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">const f</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e36"></a>Exercise 5.36:</strong> What order of evaluation does our
compiler produce for operands of a combination?  Is it left-to-right,
right-to-left, or some other order?  Where in the compiler is this order
determined?  Modify the compiler so that it produces some other order of
evaluation.  (See the discussion of order of evaluation for the
explicit-control evaluator in <a href="5_002e4.xhtml#g_t5_002e4_002e1">5.4.1</a>.)  How does changing the
order of operand evaluation affect the efficiency of the code that constructs
the argument list?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e37"></a>Exercise 5.37:</strong> One way to understand the
compiler’s <code>preserving</code> mechanism for optimizing stack usage is to see
what extra operations would be generated if we did not use this idea.  Modify
<code>preserving</code> so that it always generates the <code>save</code> and
<code>restore</code> operations.  Compile some simple expressions and identify the
unnecessary stack operations that are generated.  Compare the code to that
generated with the <code>preserving</code> mechanism intact.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e38"></a>Exercise 5.38:</strong> Our compiler is clever about
avoiding unnecessary stack operations, but it is not clever at all when it
comes to compiling calls to the primitive procedures of the language in terms
of the primitive operations supplied by the machine.  For example, consider how
much code is compiled to compute <code>(+ a 1)</code>: The code sets up an argument
list in <code>argl</code>, puts the primitive addition procedure (which it finds by
looking up the symbol <code>+</code> in the environment) into <code>proc</code>, and tests
whether the procedure is primitive or compound.  The compiler always generates
code to perform the test, as well as code for primitive and compound branches
(only one of which will be executed).  We have not shown the part of the
controller that implements primitives, but we presume that these instructions
make use of primitive arithmetic operations in the machine’s data paths.
Consider how much less code would be generated if the compiler could
<a id="index-open_002dcode"></a>
<em>open-code</em> primitives—that is, if it could generate code to directly
use these primitive machine operations.  The expression <code>(+ a 1)</code> might be
compiled into something as simple as<a class="footnote_link" id="DOCF328" href="#FOOT328"><sup>328</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">const a</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op </span><span class="pun">+</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>In this exercise we will extend our compiler to support open coding of selected
primitives.  Special-purpose code will be generated for calls to these
primitive procedures instead of the general procedure-application code.  In
order to support this, we will augment our machine with special argument
registers <code>arg1</code> and <code>arg2</code>.  The primitive arithmetic operations of
the machine will take their inputs from <code>arg1</code> and <code>arg2</code>. The
results may be put into <code>val</code>, <code>arg1</code>, or <code>arg2</code>.
</p>
<p>The compiler must be able to recognize the application of an open-coded
primitive in the source program.  We will augment the dispatch in the
<code>compile</code> procedure to recognize the names of these primitives in addition
to the reserved words (the special forms) it currently
recognizes.<a class="footnote_link" id="DOCF329" href="#FOOT329"><sup>329</sup></a> For each special
form our compiler has a code generator.  In this exercise we will construct a
family of code generators for the open-coded primitives.
</p>
<ol>
<li> The open-coded primitives, unlike the special forms, all need their operands
evaluated.  Write a code generator <code>spread-arguments</code> for use by all the
open-coding code generators.  <code>Spread-arguments</code> should take an operand
list and compile the given operands targeted to successive argument registers.
Note that an operand may contain a call to an open-coded primitive, so argument
registers will have to be preserved during operand evaluation.

</li><li> For each of the primitive procedures <code>=</code>, <code>*</code>, <code>-</code>, and
<code>+</code>, write a code generator that takes a combination with that operator,
together with a target and a linkage descriptor, and produces code to spread
the arguments into the registers and then perform the operation targeted to the
given target with the given linkage.  You need only handle expressions with two
operands.  Make <code>compile</code> dispatch to these code generators.

</li><li> Try your new compiler on the <code>factorial</code> example.  Compare the resulting
code with the result produced without open coding.

</li><li> Extend your code generators for <code>+</code> and <code>*</code> so that they can handle
expressions with arbitrary numbers of operands.  An expression with more than
two operands will have to be compiled into a sequence of operations, each with
only two inputs.

</li></ol>
</blockquote>

<a id="g_t5_002e5_002e6"></a>
<a id="Lexical-Addressing"></a>
<h4 class="subsection"><span class="secnum">5.5.6</span><span class="sectitle">Lexical Addressing</span></h4>

<p>One of the most common optimizations performed by compilers is the optimization
of variable lookup.  Our compiler, as we have implemented it so far, generates
code that uses the <code>lookup-variable-value</code> operation of the evaluator
machine.  This searches for a variable by comparing it with each variable that
is currently bound, working frame by frame outward through the run-time
environment.  This search can be expensive if the frames are deeply nested or
if there are many variables.  For example, consider the problem of looking up
the value of <code>x</code> while evaluating the expression <code>(* x y z)</code> in an
application of the procedure that is returned by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x </span><span class="lit">3</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y </span><span class="lit">4</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d e</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">y </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a b x</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">z </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> c d x</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y z</span><span class="clo">))))</span></pre></div>

<p>Since a <code>let</code> expression is just syntactic sugar for a <code>lambda</code>
combination, this expression is equivalent to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d e</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y z</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a b x</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> c d x</span><span class="clo">))))</span><span class="pln">
 </span><span class="lit">3</span><span class="pln">
 </span><span class="lit">4</span><span class="clo">)</span></pre></div>

<p>Each time <code>lookup-variable-value</code> searches for <code>x</code>, it must determine
that the symbol <code>x</code> is not <code>eq?</code> to <code>y</code> or <code>z</code> (in the
first frame), nor to <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code>, or <code>e</code> (in
the second frame).  We will assume, for the moment, that our programs do not
use <code>define</code>—that variables are bound only with <code>lambda</code>.  Because
our language is lexically scoped, the run-time environment for any expression
will have a structure that parallels the lexical structure of the program in
which the expression appears.<a class="footnote_link" id="DOCF330" href="#FOOT330"><sup>330</sup></a> Thus, the
compiler can know, when it analyzes the above expression, that each time the
procedure is applied the variable <code>x</code> in <code>(* x y z)</code> will be found
two frames out from the current frame and will be the first variable in that
frame.
</p>
<p>We can exploit this fact by inventing a new kind of variable-lookup operation,
<code>lexical-address-lookup</code>, that takes as arguments an environment and a
<a id="index-lexical-address"></a>
<em>lexical address</em> that consists of two numbers: a <a id="index-frame-number"></a>
<em>frame number</em>, 
which specifies how many frames to pass over, and a
<a id="index-displacement-number"></a>
<em>displacement number</em>, which specifies how many variables to pass over
in that frame.  <code>Lexical-address-lookup</code> will produce the value of the
variable stored at that lexical address relative to the current environment.
If we add the <code>lexical-address-lookup</code> operation to our machine, we can
make the compiler generate code that references variables using this operation,
rather than <code>lookup-variable-value</code>.  Similarly, our compiled code can use
a new <code>lexical-address-set!</code>  operation instead of
<code>set-variable-value!</code>.
</p>
<p>In order to generate such code, the compiler must be able to determine the
lexical address of a variable it is about to compile a reference to.  The
lexical address of a variable in a program depends on where one is in the code.
For example, in the following program, the address of <code>x</code> in expression
<code>⟨</code><var>e1</var><code>⟩</code> is (2, 0)—two frames back and the first variable in the frame.  At
that point <code>y</code> is at address (0, 0) and <code>c</code> is at address (1, 2).  In
expression <code>⟨</code><var>e2</var><code>⟩</code>, <code>x</code> is at (1, 0), <code>y</code> is at (1, 1), and <code>c</code>
is at (0, 2).
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d e</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y z</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">e1</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
      ⟨</span><var><span class="pln">e2</span></var><span class="pln">⟩
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> c d x</span><span class="clo">))))</span><span class="pln">
 </span><span class="lit">3</span><span class="pln">
 </span><span class="lit">4</span><span class="clo">)</span></pre></div>

<p>One way for the compiler to produce code that uses lexical addressing is to
maintain a data structure called a <a id="index-compile_002dtime-environment"></a>
<em>compile-time environment</em>.  This
keeps track of which variables will be at which positions in which frames in
the run-time environment when a particular variable-access operation is
executed.  The compile-time environment is a list of frames, each containing a
list of variables.  (There will of course be no values bound to the variables,
since values are not computed at compile time.)  The compile-time environment
becomes an additional argument to <code>compile</code> and is passed along to each
code generator.  The top-level call to <code>compile</code> uses an empty
compile-time environment.  When a <code>lambda</code> body is compiled,
<code>compile-lambda-body</code> extends the compile-time environment by a frame
containing the procedure’s parameters, so that the sequence making up the body
is compiled with that extended environment.  At each point in the compilation,
<code>compile-variable</code> and <code>compile-assignment</code> use the compile-time
environment in order to generate the appropriate lexical addresses.
</p>
<p><a href="#Exercise-5_002e39">Exercise 5.39</a> through <a href="#Exercise-5_002e43">Exercise 5.43</a> describe how to complete this
sketch of the lexical-addressing strategy in order to incorporate lexical
lookup into the compiler.  <a href="#Exercise-5_002e44">Exercise 5.44</a> describes another use for the
compile-time environment.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e39"></a>Exercise 5.39:</strong> Write a procedure
<code>lexical-address-lookup</code> that implements the new lookup operation.  It
should take two arguments—a lexical address and a run-time environment—and
return the value of the variable stored at the specified lexical address.
<code>Lexical-address-lookup</code> should signal an error if the value of the
variable is the symbol <code>*unassigned*</code>.<a class="footnote_link" id="DOCF331" href="#FOOT331"><sup>331</sup></a> Also write a procedure
<code>lexical-address-set!</code> that implements the operation that changes the
value of the variable at a specified lexical address.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e40"></a>Exercise 5.40:</strong> Modify the compiler to maintain
the compile-time environment as described above.  That is, add a
compile-time-environment argument to <code>compile</code> and the various code
generators, and extend it in <code>compile-lambda-body</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e41"></a>Exercise 5.41:</strong> Write a procedure
<code>find-variable</code> that takes as arguments a variable and a compile-time
environment and returns the lexical address of the variable with respect to
that environment.  For example, in the program fragment that is shown above,
the compile-time environment during the compilation of expression <code>⟨</code><var>e1</var><code>⟩</code> is
<code>((y z) (a b c d e) (x y))</code>.  <code>Find-variable</code> should produce
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">find-variable 
 </span><span class="lit">'c</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="pln">y z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d e</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">find-variable 
 </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="pln">y z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d e</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)))</span><span class="pln">
</span><i><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">find-variable 
 </span><span class="lit">'w</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="pln">y z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b c d e</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)))</span><span class="pln">
</span><i><span class="pln">not-found</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e42"></a>Exercise 5.42:</strong> Using <code>find-variable</code> from
<a href="#Exercise-5_002e41">Exercise 5.41</a>, rewrite <code>compile-variable</code> and
<code>compile-assignment</code> to output lexical-address instructions.  In cases
where <code>find-variable</code> returns <code>not-found</code> (that is, where the
variable is not in the compile-time environment), you should have the code
generators use the evaluator operations, as before, to search for the binding.
(The only place a variable that is not found at compile time can be is in the
global environment, which is part of the run-time environment but is not part
of the compile-time environment.<a class="footnote_link" id="DOCF332" href="#FOOT332"><sup>332</sup></a>  Thus, if you wish, you may have the evaluator operations look
directly in the global environment, which can be obtained with the operation
<code>(op get-global-environment)</code>, instead of having them search the whole
run-time environment found in <code>env</code>.)  Test the modified compiler on a few
simple cases, such as the nested <code>lambda</code> combination at the beginning of
this section.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e43"></a>Exercise 5.43:</strong> We argued in <a href="4_002e1.xhtml#g_t4_002e1_002e6">4.1.6</a>
that internal definitions for block structure should not be considered “real”
<code>define</code>s.  Rather, a procedure body should be interpreted as if the
internal variables being defined were installed as ordinary <code>lambda</code>
variables initialized to their correct values using <code>set!</code>.  
<a href="4_002e1.xhtml#g_t4_002e1_002e6">4.1.6</a> and <a href="4_002e1.xhtml#Exercise-4_002e16">Exercise 4.16</a> showed how to modify the metacircular
interpreter to accomplish this by scanning out internal definitions.  Modify
the compiler to perform the same transformation before it compiles a procedure
body.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e44"></a>Exercise 5.44:</strong> In this section we have focused
on the use of the compile-time environment to produce lexical addresses.  But
there are other uses for compile-time environments.  For instance, in
<a href="#Exercise-5_002e38">Exercise 5.38</a> we increased the efficiency of compiled code by open-coding
primitive procedures.  Our implementation treated the names of open-coded
procedures as reserved words.  If a program were to rebind such a name, the
mechanism described in <a href="#Exercise-5_002e38">Exercise 5.38</a> would still open-code it as a
primitive, ignoring the new binding.  For example, consider the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="pun">*</span><span class="pln"> a b x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b y</span><span class="clo">)))</span></pre></div>

<p>which computes a linear combination of <code>x</code> and <code>y</code>.  We might call it
with arguments <code>+matrix</code>, <code>*matrix</code>, and four matrices, but the
open-coding compiler would still open-code the <code>+</code> and the <code>*</code> in
<code>(+ (* a x) (* b y))</code> as primitive <code>+</code> and <code>*</code>.  Modify the
open-coding compiler to consult the compile-time environment in order to
compile the correct code for expressions involving the names of primitive
procedures.  (The code will work correctly as long as the program does not
<code>define</code> or <code>set!</code> these names.)
</p></blockquote>

<a id="g_t5_002e5_002e7"></a>
<a id="Interfacing-Compiled-Code-to-the-Evaluator"></a>
<h4 class="subsection"><span class="secnum">5.5.7</span><span class="sectitle">Interfacing Compiled Code to the Evaluator</span></h4>

<p>We have not yet explained how to load compiled code into the evaluator machine
or how to run it.  We will assume that the explicit-control-evaluator machine
has been defined as in <a href="5_002e4.xhtml#g_t5_002e4_002e4">5.4.4</a>, with the additional operations
specified in <a href="#Footnote-323">Footnote 323</a>.  We will implement a procedure
<code>compile-and-go</code> that compiles a Scheme expression, loads the resulting
object code into the evaluator machine, and causes the machine to run the code
in the evaluator global environment, print the result, and enter the
evaluator’s driver loop.  We will also modify the evaluator so that interpreted
expressions can call compiled procedures as well as interpreted ones.  We can
then put a compiled procedure into the machine and use the evaluator to call
it:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">compile-and-go
 </span><span class="lit">'</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="lit">1</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">))))</span><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">factorial </span><span class="lit">5</span><span class="clo">)</span><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="lit">120</span></i>
</pre></div>

<p>To allow the evaluator to handle compiled procedures (for example, to evaluate
the call to <code>factorial</code> above), we need to change the code at
<code>apply-dispatch</code> (<a href="5_002e4.xhtml#g_t5_002e4_002e1">5.4.1</a>) so that it recognizes compiled
procedures (as distinct from compound or primitive procedures) and transfers
control directly to the entry point of the compiled code:<a class="footnote_link" id="DOCF333" href="#FOOT333"><sup>333</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">apply-dispatch
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-apply</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op compound-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label compound-apply</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op compiled-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label compiled-apply</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label unknown-procedure-type</span><span class="clo">))</span><span class="pln">

compiled-apply
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op compiled-procedure-entry</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span></pre></div>

<p>Note the restore of <code>continue</code> at <code>compiled-apply</code>.  Recall that the
evaluator was arranged so that at <code>apply-dispatch</code>, the continuation would
be at the top of the stack.  The compiled code entry point, on the other hand,
expects the continuation to be in <code>continue</code>, so <code>continue</code> must be
restored before the compiled code is executed.
</p>
<p>To enable us to run some compiled code when we start the evaluator machine, we
add a <code>branch</code> instruction at the beginning of the evaluator machine,
which causes the machine to go to a new entry point if the <code>flag</code> register
is set.<a class="footnote_link" id="DOCF334" href="#FOOT334"><sup>334</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="roman"><span class="com">;; branches if </span><code><span class="com">flag</span></code><span class="com"> is set:</span></span><span class="pln">
</span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label external-entry</span><span class="clo">))</span><span class="pln"> 
read-eval-print-loop
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op initialize-stack</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="pun">…</span></span>
</pre></div>

<p><code>External-entry</code> assumes that the machine is started with <code>val</code>
containing the location of an instruction sequence that puts a result into
<code>val</code> and ends with <code>(goto (reg continue))</code>.  Starting at this entry
point jumps to the location designated by <code>val</code>, but first assigns
<code>continue</code> so that execution will return to <code>print-result</code>, which
prints the value in <code>val</code> and then goes to the beginning of the
evaluator’s read-eval-print loop.<a class="footnote_link" id="DOCF335" href="#FOOT335"><sup>335</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">external-entry
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op initialize-stack</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env </span><span class="opn">(</span><span class="pln">op get-global-environment</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label print-result</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span></pre></div>

<p>Now we can use the following procedure to compile a procedure definition,
execute the compiled code, and run the read-eval-print loop so we can try the
procedure.  Because we want the compiled code to return to the location in
<code>continue</code> with its result in <code>val</code>, we compile the expression with a
target of <code>val</code> and a linkage of <code>return</code>.  In order to transform the
object code produced by the compiler into executable instructions for the
evaluator register machine, we use the procedure <code>assemble</code> from the
register-machine simulator (<a href="5_002e2.xhtml#g_t5_002e2_002e2">5.2.2</a>).  We then initialize the
<code>val</code> register to point to the list of instructions, set the <code>flag</code>
so that the evaluator will go to <code>external-entry</code>, and start the
evaluator.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compile-and-go expression</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">instructions
         </span><span class="opn">(</span><span class="pln">assemble 
          </span><span class="opn">(</span><span class="pln">statements
           </span><span class="opn">(</span><span class="pln">compile 
            expression </span><span class="lit">'val</span><span class="pln"> </span><span class="lit">'return</span><span class="clo">))</span><span class="pln">
          eceval</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> the-global-environment
          </span><span class="opn">(</span><span class="pln">setup-environment</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">set-register-contents! 
     eceval </span><span class="lit">'val</span><span class="pln"> instructions</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">set-register-contents! 
     eceval </span><span class="lit">'flag</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">start eceval</span><span class="clo">)))</span></pre></div>

<p>If we have set up stack monitoring, as at the end of <a href="5_002e4.xhtml#g_t5_002e4_002e4">5.4.4</a>, we
can examine the stack usage of compiled code:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">compile-and-go
 </span><span class="lit">'</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="lit">1</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">))))</span><span class="pln">
</span><i><span class="opn">(</span><span class="pln">total-pushes </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">,</span><span class="pln"> maximum-depth </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">factorial </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pln">total-pushes </span><span class="pun">=</span><span class="pln"> </span><span class="lit">31</span><span class="pun">,</span><span class="pln"> maximum-depth </span><span class="pun">=</span><span class="pln"> </span><span class="lit">14</span><span class="clo">)</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="lit">120</span></i>
</pre></div>

<p>Compare this example with the evaluation of <code>(factorial 5)</code> using the
interpreted version of the same procedure, shown at the end of 
<a href="5_002e4.xhtml#g_t5_002e4_002e4">5.4.4</a>.  The interpreted version required 144 pushes and a maximum stack
depth of 28.  This illustrates the optimization that results from our
compilation strategy.
</p>
<a id="Interpretation-and-compilation"></a>
<h5 class="subsubheading">Interpretation and compilation</h5>

<p>With the programs in this section, we can now experiment with the alternative
execution strategies of interpretation and compilation.<a class="footnote_link" id="DOCF336" href="#FOOT336"><sup>336</sup></a>  An interpreter raises the machine to
the level of the user program; a compiler lowers the user program to the level
of the machine language.  We can regard the Scheme language (or any programming
language) as a coherent family of abstractions erected on the machine language.
Interpreters are good for interactive program development and debugging because
the steps of program execution are organized in terms of these abstractions,
and are therefore more intelligible to the programmer.  Compiled code can
execute faster, because the steps of program execution are organized in terms
of the machine language, and the compiler is free to make optimizations that
cut across the higher-level abstractions.<a class="footnote_link" id="DOCF337" href="#FOOT337"><sup>337</sup></a>
</p>
<p>The alternatives of interpretation and compilation also lead to different
strategies for porting languages to new computers. Suppose that we wish to
implement Lisp for a new machine.  One strategy is to begin with the
explicit-control evaluator of <a href="5_002e4.xhtml#g_t5_002e4">5.4</a> and translate its instructions
to instructions for the new machine.  A different strategy is to begin with the
compiler and change the code generators so that they generate code for the new
machine.  The second strategy allows us to run any Lisp program on the new
machine by first compiling it with the compiler running on our original Lisp
system, and linking it with a compiled version of the run-time
library.<a class="footnote_link" id="DOCF338" href="#FOOT338"><sup>338</sup></a> Better yet, we can
compile the compiler itself, and run this on the new machine to compile other
Lisp programs.<a class="footnote_link" id="DOCF339" href="#FOOT339"><sup>339</sup></a>  Or we can compile one of the interpreters of 
<a href="4_002e1.xhtml#g_t4_002e1">4.1</a> to produce an interpreter that runs on the new machine.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e45"></a>Exercise 5.45:</strong> By comparing the stack operations
used by compiled code to the stack operations used by the evaluator for the
same computation, we can determine the extent to which the compiler optimizes
use of the stack, both in speed (reducing the total number of stack operations)
and in space (reducing the maximum stack depth).  Comparing this optimized
stack use to the performance of a special-purpose machine for the same
computation gives some indication of the quality of the compiler.
</p>
<ol>
<li> <a href="5_002e4.xhtml#Exercise-5_002e27">Exercise 5.27</a> asked you to determine, as a function of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, the number
of pushes and the maximum stack depth needed by the evaluator to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>
using the recursive factorial procedure given above.  <a href="5_002e2.xhtml#Exercise-5_002e14">Exercise 5.14</a> asked
you to do the same measurements for the special-purpose factorial machine shown
in <a href="5_002e1.xhtml#Figure-5_002e11">Figure 5.11</a>. Now perform the same analysis using the compiled
<code>factorial</code> procedure.

<p>Take the ratio of the number of pushes in the compiled version to the number of
pushes in the interpreted version, and do the same for the maximum stack depth.
Since the number of operations and the stack depth used to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>  are
linear in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, these ratios should approach constants as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> becomes large.
What are these constants?  Similarly, find the ratios of the stack usage in the
special-purpose machine to the usage in the interpreted version.
</p>
<p>Compare the ratios for special-purpose versus interpreted code to the ratios
for compiled versus interpreted code.  You should find that the special-purpose
machine does much better than the compiled code, since the hand-tailored
controller code should be much better than what is produced by our rudimentary
general-purpose compiler.
</p>
</li><li> Can you suggest improvements to the compiler that would help it generate code
that would come closer in performance to the hand-tailored version?

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e46"></a>Exercise 5.46:</strong> Carry out an analysis like the
one in <a href="#Exercise-5_002e45">Exercise 5.45</a> to determine the effectiveness of compiling the
tree-recursive Fibonacci procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">)</span><span class="pln">
      n
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">)))))</span></pre></div>

<p>compared to the effectiveness of using the special-purpose Fibonacci machine of
<a href="5_002e1.xhtml#Figure-5_002e12">Figure 5.12</a>.  (For measurement of the interpreted performance, see
<a href="5_002e4.xhtml#Exercise-5_002e29">Exercise 5.29</a>.)  For Fibonacci, the time resource used is not linear in
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>;</mo>
  </mrow>
</math> hence the ratios of stack operations will not approach a limiting value
that is independent of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e47"></a>Exercise 5.47:</strong> This section described how to
modify the explicit-control evaluator so that interpreted code can call
compiled procedures.  Show how to modify the compiler so that compiled
procedures can call not only primitive procedures and compiled procedures, but
interpreted procedures as well.  This requires modifying
<code>compile-procedure-call</code> to handle the case of compound (interpreted)
procedures.  Be sure to handle all the same <code>target</code> and <code>linkage</code>
combinations as in <code>compile-proc-appl</code>.  To do the actual procedure
application, the code needs to jump to the evaluator’s <code>compound-apply</code>
entry point.  This label cannot be directly referenced in object code (since
the assembler requires that all labels referenced by the code it is assembling
be defined there), so we will add a register called <code>compapp</code> to the
evaluator machine to hold this entry point, and add an instruction to
initialize it:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">  </span><span class="opn">(</span><span class="pln">assign compapp </span><span class="opn">(</span><span class="pln">label compound-apply</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="com">;; branches if </span><code><span class="com">flag</span></code><span class="com"> is set:</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label external-entry</span><span class="clo">))</span><span class="pln">
read-eval-print-loop </span><span class="roman"><span class="pun">…</span></span>
</pre></div>

<p>To test your code, start by defining a procedure <code>f</code> that calls a
procedure <code>g</code>.  Use <code>compile-and-go</code> to compile the definition of
<code>f</code> and start the evaluator.  Now, typing at the evaluator, define
<code>g</code> and try to call <code>f</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e48"></a>Exercise 5.48:</strong> The <code>compile-and-go</code>
interface implemented in this section is awkward, since the compiler can be
called only once (when the evaluator machine is started).  Augment the
compiler-interpreter interface by providing a <code>compile-and-run</code> primitive
that can be called from within the explicit-control evaluator as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">compile-and-run
 </span><span class="lit">'</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="lit">1</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">))))</span><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">factorial </span><span class="lit">5</span><span class="clo">)</span><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="lit">120</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e49"></a>Exercise 5.49:</strong> As an alternative to using the
explicit-control evaluator’s read-eval-print loop, design a register machine
that performs a read-compile-execute-print loop.  That is, the machine should
run a loop that reads an expression, compiles it, assembles and executes the
resulting code, and prints the result.  This is easy to run in our simulated
setup, since we can arrange to call the procedures <code>compile</code> and
<code>assemble</code> as “register-machine operations.”
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e50"></a>Exercise 5.50:</strong> Use the compiler to compile the
metacircular evaluator of <a href="4_002e1.xhtml#g_t4_002e1">4.1</a> and run this program using the
register-machine simulator.  (To compile more than one definition at a time,
you can package the definitions in a <code>begin</code>.)  The resulting interpreter
will run very slowly because of the multiple levels of interpretation, but
getting all the details to work is an instructive exercise.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e51"></a>Exercise 5.51:</strong> Develop a rudimentary
implementation of Scheme in C (or some other low-level language of your choice)
by translating the explicit-control evaluator of <a href="5_002e4.xhtml#g_t5_002e4">5.4</a> into C.  In
order to run this code you will need to also provide appropriate
storage-allocation routines and other run-time support.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e52"></a>Exercise 5.52:</strong> As a counterpoint to 
<a href="#Exercise-5_002e51">Exercise 5.51</a>, modify the compiler so that it compiles Scheme procedures
into sequences of C instructions.  Compile the metacircular evaluator of
<a href="4_002e1.xhtml#g_t4_002e1">4.1</a> to produce a Scheme interpreter written in C.
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT318"><p><a class="footnote_backlink" href="#DOCF318"><sup>318</sup></a>
This is a theoretical statement.  We are not claiming that
the evaluator’s data paths are a particularly convenient or efficient set of
data paths for a general-purpose computer.  For example, they are not very good
for implementing high-performance floating-point calculations or calculations
that intensively manipulate bit vectors.</p>
</div>
<div id="FOOT319"><p><a class="footnote_backlink" href="#DOCF319"><sup>319</sup></a>
Actually, the machine that runs compiled code can be simpler
than the interpreter machine, because we won’t use the <code>exp</code> and
<code>unev</code> registers.  The interpreter used these to hold pieces of
unevaluated expressions.  With the compiler, however, these expressions get
built into the compiled code that the register machine will run.  For the same
reason, we don’t need the machine operations that deal with expression syntax.
But compiled code will use a few additional machine operations (to represent
compiled procedure objects) that didn’t appear in the explicit-control
evaluator machine.</p>
</div>
<div id="FOOT320"><p><a class="footnote_backlink" href="#DOCF320"><sup>320</sup></a>
Notice, however, that our compiler is a Scheme
program, and the syntax procedures that it uses to manipulate expressions are
the actual Scheme procedures used with the metacircular evaluator.  For the
explicit-control evaluator, in contrast, we assumed that equivalent syntax
operations were available as operations for the register machine.  (Of course,
when we simulated the register machine in Scheme, we used the actual Scheme
procedures in our register machine simulation.)</p>
</div>
<div id="FOOT321"><p><a class="footnote_backlink" href="#DOCF321"><sup>321</sup></a>
This procedure
uses a feature of Lisp called <a id="index-backquote"></a>
<em>backquote</em> (or <a id="index-quasiquote"></a>
<em>quasiquote</em>)
that is handy for constructing lists.  Preceding a list with a backquote symbol
is much like quoting it, except that anything in the list that is flagged with
a comma is evaluated.
</p>
<p>For example, if the value of <code>linkage</code> is the symbol <code>branch25</code>,
then the expression 
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pun">`</span><span class="opn">((</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label </span><span class="pun">,</span><span class="pln">linkage</span><span class="clo">)))</span></pre></div>

<p>evaluates to the list 
</p>	
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label branch25</span><span class="clo">)))</span><span class="pln"> </span></pre></div>

<p>Similarly, if the value of <code>x</code> is the list <code>(a b c)</code>, then 
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pun">`</span><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="pun">,</span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">))</span><span class="pln"> </span></pre></div>

<p>evaluates to the list 
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> a</span><span class="clo">)</span></pre></div>
</div>
<div id="FOOT322"><p><a class="footnote_backlink" href="#DOCF322"><sup>322</sup></a>
We can’t just use the labels <code>true-branch</code>,
<code>false-branch</code>, and <code>after-if</code> as shown above, because there might be
more than one <code>if</code> in the program.  The compiler uses the procedure
<code>make-label</code> to generate labels.  <code>Make-label</code> takes a symbol as
argument and returns a new symbol that begins with the given symbol.  For
example, successive calls to <code>(make-label 'a)</code> would return <code>a1</code>,
<code>a2</code>, and so on.  <code>Make-label</code> can be implemented similarly to the
generation of unique variable names in the query language, as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> label-counter </span><span class="lit">0</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">new-label-number</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> label-counter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> label-counter</span><span class="clo">))</span><span class="pln">
  label-counter</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-label name</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">string-</span><span class="pun">&gt;</span><span class="pln">symbol
   </span><span class="opn">(</span><span class="pln">string-append 
    </span><span class="opn">(</span><span class="pln">symbol-</span><span class="pun">&gt;</span><span class="pln">string name</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">number-</span><span class="pun">&gt;</span><span class="pln">string </span><span class="opn">(</span><span class="pln">new-label-number</span><span class="clo">)))))</span></pre></div>
</div>
<div id="FOOT323"><p><a class="footnote_backlink" href="#DOCF323"><sup>323</sup></a>
<a id="Footnote-323"></a>We need
machine operations to implement a data structure for representing compiled
procedures, analogous to the structure for compound procedures described in
<a href="4_002e1.xhtml#g_t4_002e1_002e3">4.1.3</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-compiled-procedure entry env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'compiled-procedure</span><span class="pln"> entry env</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compiled-procedure? proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">tagged-list? proc </span><span class="lit">'compiled-procedure</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compiled-procedure-entry c-proc</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> c-proc</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">compiled-procedure-env c-proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">caddr</span><span class="pln"> c-proc</span><span class="clo">))</span></pre></div>
</div>
<div id="FOOT324"><p><a class="footnote_backlink" href="#DOCF324"><sup>324</sup></a>
Actually, we signal an error when the target is not
<code>val</code> and the linkage is <code>return</code>, since the only place we request
<code>return</code> linkages is in compiling procedures, and our convention is that
procedures return their values in <code>val</code>.</p>
</div>
<div id="FOOT325"><p><a class="footnote_backlink" href="#DOCF325"><sup>325</sup></a>
Making a compiler generate tail-recursive code might seem like
a straightforward idea.  But most compilers for common languages, including C
and Pascal, do not do this, and therefore these languages cannot represent
iterative processes in terms of procedure call alone.  The difficulty with tail
recursion in these languages is that their implementations use the stack to
store procedure arguments and local variables as well as return addresses.  The
Scheme implementations described in this book store arguments and variables in
memory to be garbage-collected.  The reason for using the stack for variables
and arguments is that it avoids the need for garbage collection in languages
that would not otherwise require it, and is generally believed to be more
efficient.  Sophisticated Lisp compilers can, in fact, use the stack for
arguments without destroying tail recursion.  (See <a href="References.xhtml#Hanson-1990">Hanson 1990</a> for a
description.)  There is also some debate about whether stack allocation is
actually more efficient than garbage collection in the first place, but the
details seem to hinge on fine points of computer architecture.  (See <a href="References.xhtml#Appel-1987">Appel 1987</a>
and <a href="References.xhtml#Miller-and-Rozas-1994">Miller and Rozas 1994</a> for opposing views on this issue.)</p>
</div>
<div id="FOOT326"><p><a class="footnote_backlink" href="#DOCF326"><sup>326</sup></a>
The
variable <code>all-regs</code> is bound to the list of names of all the registers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> all-regs </span><span class="lit">'</span><span class="opn">(</span><span class="pln">env proc val argl continue</span><span class="clo">))</span></pre></div>
</div>
<div id="FOOT327"><p><a class="footnote_backlink" href="#DOCF327"><sup>327</sup></a>
Note that <code>preserving</code> calls
<code>append</code> with three arguments.  Though the definition of <code>append</code>
shown in this book accepts only two arguments, Scheme standardly provides an
<code>append</code> procedure that takes an arbitrary number of arguments.</p>
</div>
<div id="FOOT328"><p><a class="footnote_backlink" href="#DOCF328"><sup>328</sup></a>
We have used the same symbol
<code>+</code> here to denote both the source-language procedure and the machine
operation.  In general there will not be a one-to-one correspondence between
primitives of the source language and primitives of the machine.</p>
</div>
<div id="FOOT329"><p><a class="footnote_backlink" href="#DOCF329"><sup>329</sup></a>
Making the primitives into reserved words is in general a
bad idea, since a user cannot then rebind these names to different procedures.
Moreover, if we add reserved words to a compiler that is in use, existing
programs that define procedures with these names will stop working.  See
<a href="#Exercise-5_002e44">Exercise 5.44</a> for ideas on how to avoid this problem.</p>
</div>
<div id="FOOT330"><p><a class="footnote_backlink" href="#DOCF330"><sup>330</sup></a>
This is not true if we allow internal
definitions, unless we scan them out.  See <a href="#Exercise-5_002e43">Exercise 5.43</a>.  </p>
</div>
<div id="FOOT331"><p><a class="footnote_backlink" href="#DOCF331"><sup>331</sup></a>
This is the modification
to variable lookup required if we implement the scanning method to eliminate
internal definitions (<a href="#Exercise-5_002e43">Exercise 5.43</a>).  We will need to eliminate these
definitions in order for lexical addressing to work.</p>
</div>
<div id="FOOT332"><p><a class="footnote_backlink" href="#DOCF332"><sup>332</sup></a>
Lexical addresses cannot be used to
access variables in the global environment, because these names can be defined
and redefined interactively at any time.  With internal definitions scanned
out, as in <a href="#Exercise-5_002e43">Exercise 5.43</a>, the only definitions the compiler sees are
those at top level, which act on the global environment.  Compilation of a
definition does not cause the defined name to be entered in the compile-time
environment.</p>
</div>
<div id="FOOT333"><p><a class="footnote_backlink" href="#DOCF333"><sup>333</sup></a>
Of course,
compiled procedures as well as interpreted procedures are compound
(nonprimitive).  For compatibility with the terminology used in the
explicit-control evaluator, in this section we will use “compound” to mean
interpreted (as opposed to compiled).</p>
</div>
<div id="FOOT334"><p><a class="footnote_backlink" href="#DOCF334"><sup>334</sup></a>
Now that the evaluator machine starts with a <code>branch</code>, we
must always initialize the <code>flag</code> register before starting the evaluator
machine.  To start the machine at its ordinary read-eval-print loop, we could
use
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">start-eceval</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> the-global-environment
        </span><span class="opn">(</span><span class="pln">setup-environment</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">set-register-contents! eceval </span><span class="lit">'flag</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">start eceval</span><span class="clo">))</span></pre></div>
</div>
<div id="FOOT335"><p><a class="footnote_backlink" href="#DOCF335"><sup>335</sup></a>
Since a compiled procedure is an
object that the system may try to print, we also modify the system print
operation <code>user-print</code> (from <a href="4_002e1.xhtml#g_t4_002e1_002e4">4.1.4</a>) so that it will not
attempt to print the components of a compiled procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">user-print object</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">compound-procedure? object</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">display 
          </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'compound-procedure</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">procedure-parameters object</span><span class="clo">)</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">procedure-body object</span><span class="clo">)</span><span class="pln">
                </span><span class="lit">'</span><span class="pun">&lt;</span><span class="pln">procedure-env</span><span class="pun">&gt;</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">compiled-procedure? object</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">display </span><span class="lit">'</span><span class="pun">&lt;</span><span class="pln">compiled-procedure</span><span class="pun">&gt;</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display object</span><span class="clo">))))</span></pre></div>
</div>
<div id="FOOT336"><p><a class="footnote_backlink" href="#DOCF336"><sup>336</sup></a>
We can do even
better by extending the compiler to allow compiled code to call interpreted
procedures.  See <a href="#Exercise-5_002e47">Exercise 5.47</a>.</p>
</div>
<div id="FOOT337"><p><a class="footnote_backlink" href="#DOCF337"><sup>337</sup></a>
Independent of the strategy
of execution, we incur significant overhead if we insist that errors
encountered in execution of a user program be detected and signaled, rather
than being allowed to kill the system or produce wrong answers.  For example,
an out-of-bounds array reference can be detected by checking the validity of
the reference before performing it.  The overhead of checking, however, can be
many times the cost of the array reference itself, and a programmer should
weigh speed against safety in determining whether such a check is desirable.  A
good compiler should be able to produce code with such checks, should avoid
redundant checks, and should allow programmers to control the extent and type
of error checking in the compiled code.
</p>
<p>Compilers for popular languages, such as C and C++, put hardly any
error-checking operations into running code, so as to make things run as fast
as possible.  As a result, it falls to programmers to explicitly provide error
checking.  Unfortunately, people often neglect to do this, even in critical
applications where speed is not a constraint.  Their programs lead fast and
dangerous lives.  For example, the notorious “Worm” that paralyzed the
Internet in 1988 exploited the <abbr>UNIX</abbr>(tm) operating system’s failure to
check whether the input buffer has overflowed in the finger daemon. (See
<a href="References.xhtml#Spafford-1989">Spafford 1989</a>.)</p>
</div>
<div id="FOOT338"><p><a class="footnote_backlink" href="#DOCF338"><sup>338</sup></a>
Of course, with either the interpretation or the compilation
strategy we must also implement for the new machine storage allocation, input
and output, and all the various operations that we took as “primitive” in our
discussion of the evaluator and compiler.  One strategy for minimizing work
here is to write as many of these operations as possible in Lisp and then
compile them for the new machine.  Ultimately, everything reduces to a small
kernel (such as garbage collection and the mechanism for applying actual
machine primitives) that is hand-coded for the new machine.</p>
</div>
<div id="FOOT339"><p><a class="footnote_backlink" href="#DOCF339"><sup>339</sup></a>
This strategy leads to amusing tests of correctness of
the compiler, such as checking whether the compilation of a program on the new
machine, using the compiled compiler, is identical with the compilation of the
program on the original Lisp system.  Tracking down the source of differences
is fun but often frustrating, because the results are extremely sensitive to
minuscule details.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="References.xhtml#References" accesskey="n" rel="next">References</a>, Prev: <a href="5_002e4.xhtml#g_t5_002e4" accesskey="p" rel="prev">5.4</a>, Up: <a href="#g_t5_002e5" accesskey="u" rel="prev">5.5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>